1 条题解
-
0XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2023-10-21 10:30:26
SPFA代码参考P1023 题解
因为SPFA中的点有可能会重复入队,没有vis标记。如果有负环的话,SPFA肯定会陷入死循环。
那么只需要略作修改,统计一下入队次数就可以。// 只给出部分代码,其他见P1023题解 queue<int> q; int cnt[MAXN]; bool SPFA(int s){ // 有负环返回true for(int i=0; i<=n; i++) dis[i] = INF; // 初始化为无穷大 dis[s] = 0; vis[s] = true; // 标记该点 cnt[s]++; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=h[u]; i; i=nxt[i]){ int v=to[i]; if(dis[v]>dis[u]+val[i]){ // 如果可以松弛 dis[v]=dis[u]+val[i]; q.push(v); // 松弛后入队 cnt[v]++; if (cnt[v] > n) return true; // 找到入队次数大于n的点,存在可到达的负环 } } } return false; }
- 1