从节点 1 运行 SPFA，以最短路边数达到 n 判断可达负环。
OJ: luogu
题目 ID: P3385
难度:普及+/提高-
标签:负环SPFA最短路python
日期: 2026-07-17 03:00
题意
判断从节点 1 能到达的区域内是否存在负环。
思路
只把 1 入队做 SPFA。每次成功松弛时记录新路径边数 count[v]=count[u]+1；简单最短路至多含 n-1 条边，达到 n 说明存在可不断缩短的环。
Python 知识
deque实现松弛队列，bytearray保存入队状态。- 正边按题意添加双向，负边只添加输入方向。
- 多组答案最后统一
join输出。
代码
python
import sys
from collections import deque
input = sys.stdin.buffer.readline
answers = []
for _ in range(int(input())):
n, descriptions = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for __ in range(descriptions):
u, v, weight = map(int, input().split())
graph[u].append((v, weight))
if weight >= 0:
graph[v].append((u, weight))
infinity = 10**30
distance = [infinity] * (n + 1)
edge_count = [0] * (n + 1)
in_queue = bytearray(n + 1)
distance[1] = 0
queue = deque([1])
in_queue[1] = 1
negative_cycle = False
while queue and not negative_cycle:
node = queue.popleft()
in_queue[node] = 0
for neighbor, weight in graph[node]:
candidate = distance[node] + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
edge_count[neighbor] = edge_count[node] + 1
if edge_count[neighbor] >= n:
negative_cycle = True
break
if not in_queue[neighbor]:
queue.append(neighbor)
in_queue[neighbor] = 1
answers.append("YES" if negative_cycle else "NO")
print("\n".join(answers))原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-17 01:40
* update_at: 2026-07-17 01:40
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
SPFA 最坏 O(nm)，空间 O(n+m)。
总结
题目只问从 1 可达的负环，不能把所有节点无条件作为同一可达源处理。