我的第一道洛谷题：^_^
思路:
1.初始化（不然会有悲剧发生，我就经历过）
memset(head, 0, sizeof(head)); memset(exsit, 0, sizeof(exsit)); memset(d, 0x3f, sizeof(d)); memset(count, 0, sizeof(count));
2.建图（非常简单的一步~）
inline void addEdge(int x, int y, int z) { G[++num].to=y; G[num].data=z; G[num].next=head[x]; head[x]=num; }
3.spfa（简单模板）
inline bool spfa(int x) { d[x] = 0; exsit[x] = 1; q.push(x); count[x] = 1; while(!q.empty()) { int u = q.front(); q.pop(); exsit[u] = 0; for(int i=head[u]; i; i = G[i].next) { int v = G[i].to; int w = G[i].data; if(d[v] > d[u] + w) { d[v] = d[u] + w; if(!exsit[v]) { count[v]++; if(count[v] > n-1) return false; exsit[v] = 1; q.push(v); } } } } return true; }
有没有感觉异常简单呢？只是一道基础模板题而已。只是输出上有点小坑，一定要看清题啊！！！！！！！！！
贴个完整代码吧：
#include <iostream> #include <cstring> #include <queue> #include <vector> #include <cstdio> #define F(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int MAXN = 6000; const int MAXM = 60000; int n, m, num, T; int head[MAXN], exsit[MAXN], d[MAXN], count[MAXN]; queue <int> q; struct Edge { int to, data, next; }G[MAXM]; inline void addEdge(int x, int y, int z) { G[++num].to=y; G[num].data=z; G[num].next=head[x]; head[x]=num; } inline bool spfa(int x) { d[x] = 0; exsit[x] = 1; q.push(x); count[x] = 1; while(!q.empty()) { int u = q.front(); q.pop(); exsit[u] = 0; for(int i=head[u]; i; i = G[i].next) { int v = G[i].to; int w = G[i].data; if(d[v] > d[u] + w) { d[v] = d[u] + w; if(!exsit[v]) { count[v]++; if(count[v] > n-1) return false; exsit[v] = 1; q.push(v); } } } } return true; } int main() { cin >> T; while(T--) { memset(head, 0, sizeof(head)); memset(exsit, 0, sizeof(exsit)); memset(d, 0x3f, sizeof(d)); memset(count, 0, sizeof(count)); while(!q.empty()) q.pop(); n = read(); m = read(); int a, b, c; F(i,1,m) { a = read(); b = read(); c = read(); if(c < 0) { addEdge(a, b, c); } else { addEdge(a, b, c); addEdge(b, a, c); } } if(!spfa(1)) cout << "YE5" << endl; else cout << "N0" << endl; } return 0; }
最后， 别忘了开o2，最好用Bellman_Ford哦~(有没有感觉被骗了,逃
原文：https://www.cnblogs.com/Ghostyht/p/9251577.html