【题解】

精DJ落泪
这题要用铃铛人（bushi
或者SPFA（带负）代码如下：

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

const int N = 1e3 + 5;
const int INF = 0x3c;
vector<pair<int,int> > g[N];
//我这里用的是pair，struct也可以
int dist[N],vis[N];
//dist不用多说，vis是用来判断负环的

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});
        //attention：有向图
    }
    queue<int> q;
    memset(dist,INF,sizeof dist);
    //dist数组初始化为正无穷，好在松弛的时候直接比较
    dist[s] = 0;
    q.push(s);
    while(!q.empty()){
        int ip = q.front();
        q.pop();
        vis[ip] ++;
        if(vis[ip] > n){
            //图中n个点，这代表如果最坏时每个点都对此松弛一遍，也不会松弛超过n次。因此必有负环。
            cout << "no solution";
            return 0;
        }
        for(auto node : g[ip]){
            int v = node.first,w = node.second;
            if(dist[v] > dist[ip] + w){//如果优于之前的路线就松弛。
                dist[v] = dist[ip] + w;
                q.push(v);
            }
        }
    }
    for(int i = 1;i <= n;i ++){
        if(dist[i] == 0x3c3c3c3c) cout << "-1 ";//差点忘了输出-1，即正无穷时
        else cout << dist[i] << " ";
    }
    return 0;
}