495. spfa判断负环
时间限制：1000 MS 内存限制：64 MB
题目描述
# spfa判断负环 ## 题目描述 给定一个包含 $n$ 个顶点、$m$ 条边的有向图，顶点编号为 $1$ 到 $n$。图中允许存在重边和自环，边权可能为负数。 请判断整个图中是否存在负权回路。负权回路是指沿有向边行走后回到起点，且经过的边的权值之和小于 $0$ 的回路。 图可能不连通，你需要检测整个图中的负权回路，而不限于从某个指定顶点能够到达的部分。 ## 输入格式 从文件 `spfan.in` 中读入数据。 第一行包含两个整数 $n,m$，分别表示顶点数和边数。 接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示一条从顶点 $x$ 到顶点 $y$、权值为 $z$ 的有向边。 ## 输出格式 将结果输出到文件 `spfan.out`。 如果图中存在负权回路，输出 `Yes`；否则输出 `No`。 ## 数据范围 - $1 \le n \le 2000$。 - $1 \le m \le 10000$。 - $1 \le x,y \le n$。 - 边权 $z$ 为整数，且 $|z| \le 10000$。 - 图为有向图，允许存在重边和自环。 ## 样例输入 ``` 3 3 1 2 -1 2 3 4 3 1 -4 ``` ## 样例输出 ``` Yes ``` ## 样例说明 回路 $1 \to 2 \to 3 \to 1$ 的边权之和为 $-1+4-4=-1$，因此图中存在负权回路。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$64$ MB。