最近很久没怎么写最短路的题导致这个题交了好多遍
AC率是怎么下来的自己心里没点数
SPFA虽然臭名昭著但是他可以用来判负环
如果一个点进队的次数大于等于n说明存在负环
这道题一开始memset我给dis赋了零
在SPFA厨师第一个点的时候根本就忘了还要初始化dis
菜死了
还有这题变态没让着输出YES或者NO
他让着输出YE5和N0......虽然我一眼就看出来了但是我还是把E写成了小写的....
Code：
//SPFA判断负环 #include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 250000; int head[N << 1], n, m, cnt, tim[N], T, dis[N]; struct node { int nxt, to, w; }e[N << 1]; bool vis[N]; int read() { int s = 0, w = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} return s * w; } void add(int x, int y, int z) { e[++cnt].nxt = head[x]; e[cnt].to = y; e[cnt].w = z; head[x] = cnt; } bool spfa() { queue<int> q; q.push(1); vis[1] = 1; dis[1] = 0; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; if(!vis[v]) { tim[v]++; q.push(v); vis[v] = 1; if(tim[v] >= n) return 1; } } } } return 0; } int main() { T = read(); while(T--) { memset(vis, 0, sizeof(vis)); memset(head, 0, sizeof(head)); memset(tim, 0, sizeof(tim)); memset(dis, 0x3f3f3f3f, sizeof(dis)); n = read(), m = read(); for(int i = 1, x, y, z; i <= m; i++) { x = read(), y = read(), z = read(); if(z < 0) add(x, y, z); else add(x, y, z), add(y, x, z); } if(spfa()) printf("YE5\n"); else printf("N0\n"); } return 0; }