Spfa求调

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500005, M = 500010;
const int inf = pow(2,31)-1;
struct Edge
{
    int to, nxt, w;
}e[M];
int cnt;
int dis[N],head[N];
int cnt1[N],vis[N]; 
int n, m, s;
queue<int> q;
void add(int u,int v,int w)
{
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
bool spfa()
{
    for(int i=0; i<=500000; i++) dis[i] = inf;
    dis[s] = 0; vis[s] = 1;
    q.push(s);
    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, w = e[i].w;
    		if(dis[v] > dis[u]+w)
    		{
    			dis[v] = dis[u]+w;
    			cnt1[v] = cnt1[u]+1;
    			if(cnt1[v] >= n) return false;
    			if(vis[v] == 0)
    			{
    				q.push(v); vis[v] = 1;
				}
			}
		}
    }
    return 1;
}

signed main()
{
	ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a,b,w);	
    }
    bool flag = spfa();
    for(int i=1; i<=n; i++) cout<<dis[i]<<" ";
    return 0;
}