题解 带注释

很早就学过了，原汁原味的铃铛人算法，尽量少写注释但是还是让你知道，你复制的是Bellman-Ford算法

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
// 我才知道pair<type, type>在这个库里面
using namespace std;
typedef long long ll;
const ll N = 1e3 + 5;
ll n, m, s;
vector<pair<ll, ll>> mp[N];
ll dis[N];
int main(){
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        mp[u].push_back({v, w});// 邻接表存储图
    }
    for(int i=1; i<=n; i++){
        dis[i] = 1e18;// 距离数组初始化无穷大
    }
    dis[s] = 0;// 起始点距离为0
    queue<pair<ll, ll>> q;// 记录起始节点
    q.push({s, 0});
    ll cnt[N] = {};// 记录取用次数，最高n-1，超过就是负环
    while(q.size()){
        ll u = q.front().first;
        ll d = q.front().second;
        q.pop();
        for(int i=0; i<mp[u].size(); i++){
            ll to = mp[u][i].first;
            ll len = mp[u][i].second;
            if(dis[to] > dis[u] + len){
                dis[to] = dis[u] + len;// 距离数组维护
                q.push({to, d + len});
                cnt[to]++;
                if(cnt[to] >= n){
                    cout << "no solution" << endl;
                    return 0; // 产生负环
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        if(dis[i] == 1e18) cout << -1 << " "; // 如果任然为1e18，说明无法到达
        else cout << dis[i] << " ";
    }
    return 0;
}