题解

我用的SPFA，其实Floyd暴力也能过

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e3+7;
const int INF=2e9;
struct node{
int v,w;
};
vector<node>g[N];
int main(){
    int n,m,s;
    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});
    }
    vector<int>dis(n+1,INF);
    vector<bool>vis(n+1,false);//判断当前点是否在队列
    vector<int>cnt(n+1,0);//记录入队次数
    dis[s]=0;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int u=q.front();//当前点
        q.pop();
        vis[u]=false;//出队
        for(auto [v,w]:g[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=true;
                    cnt[v]++;
                    if(cnt[v]>=n){
                        cout<<"no solution\n";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==INF)cout<<"-1 ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}