那请帮我改正一下
时间: 2024-02-12 22:07:55 浏览: 63
可以在 SPFA 算法中增加对负环的判断,如果在某个点进队的次数超过 n 次,那么说明存在负环,直接返回 false 即可。修改后的代码如下:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010, M = 2000010;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx; // 邻接表存图
int dist[N]; // 存储起点到各个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
int cnt[N]; // 存储每个点进队的次数
int q[N]; // 手写队列
void add(int a, int b, int c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
bool spfa(){
memset(dist, 0x3f, sizeof dist); // 初始化 dist 数组,全部赋为 INF
dist[s] = 0;
int hh = 0, tt = 0;
q[tt ++ ] = s;
st[s] = true;
while (hh != tt) {
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) // 遍历 t 的所有出边
{
int j = e[i];
if (dist[j] > dist[t] + w[i]) // 如果从 t 点到 j 点的距离更短
{
dist[j] = dist[t] + w[i]; // 更新 dist[j]
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) // 如果存在正环,直接返回 false
return false;
if (!st[j]) // 如果 j 还没在队列中
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return true;
}
int main(){
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
if (spfa())
cout << dist[t] << endl;
else
puts("无解");
return 0;
}
```