写了一个 SPFA,写了 231−1,但是还是错了。有没有大佬能帮我看下,谢谢。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, M = 5e5 + 5;
struct node
{
int v, w;
};
bool vis[N];
int n, m, s, dist[N];
vector <node> g[N];
void spfa()
{
queue <int> q;
q.push(s);
memset(dist, 0x7f, sizeof dist);
vis[s] = true, dist[s] = 0;
while (!q.empty())
{
int now = q.front(); q.pop(); vis[now] = false;
for (int i = 0; i < g[now].size(); i++)
{
int v = g[now][i].v, w = g[now][i].w;
if (dist[now] != 0x7f && dist[now] + w < dist[v])
{
dist[v] = dist[now] + w;
if (!vis[v]) q.push(v), vis[v] = true;
}
}
}
for (int i = 1; i <= n; i++)
{
if (dist[i] == 0x7f) cout << "2147483647 ";
else cout << dist[i] << " ";
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
spfa();
return 0;
}