bellmanford #1TLE 悬关QAQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
int n,m,s;
int ans[N];
struct node{
    int v,w;
};
vector<node> vt[N];
void chushihua(){
    for(int i=1;i<=n;++i) ans[i]=inf;
    ans[s]=0;
    return ;
}
void bellmanford(){
    for(int i=1;i<=n;++i){
        bool flag=0;
        for(int u=1;u<=n;++u){
            if(ans[u]==inf) continue;
            for(auto ed:vt[u]){
                int v=ed.v, w=ed.w;
                if(ans[u]+w<ans[v]){
                    ans[v]=ans[u]+w;
                    flag=1;
                }
            }
        }
        if(!flag) break;
    }
    return ;
}
signed main(){
    cin>>n>>m>>s;
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        vt[x].push_back({y,z});
    }
    chushihua();
    bellmanford();
    for(int i=1;i<=n;++i)
        cout<<ans[i]<<' ';
    return 0;
}

感谢大佬！
感谢大佬！！
感谢大佬！！！
感谢大佬！！！！
感谢大佬！！！！！