【悬关】SPFA 模版 TLE 40pts 求条

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

int n, m, s;
struct Edge
{
    int v, w;
};
vector<Edge> e[10005];
int u, v, w;

int vis[10005];
int dis[10005];
int cnt[10005];

void spfa()
{
    queue<int> q;
	for(int i = 1; i <= n; i++)
        dis[i] = 2147483647;
    dis[s] = 0, vis[s] = 1;
    q.push(s);
    while(q.size())
    {
        auto f = q.front();
        q.pop();
        vis[f] = 0;
        for(auto [i, j] : e[f])
        {
            if(dis[i] > dis[f] + j)
            {
                dis[i] = dis[f] + j;
                cnt[i] = cnt[f] + 1;
                if(cnt[i] >= n) return;
              	if(!vis[i]) q.push(i), vis[i] = 1;
            }
        }
    }
    
}
signed main()
{
	cin >> n >> m >> s;
    for(int i = 1; i <= m; i++)
        cin >> u >> v >> w,
    	e[u].push_back({v, w}),
    	
    spfa();

    for(int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
    
    return 0;
}