题解DJ斯特拉

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10, inf = 0x3f3f3f3f;

vector<pair<int, int>> g[N];
int vis[N], dis[N];
int n, m, s;
void dij(int s){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;
    memset(dis, inf, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while(q.size()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < g[x].size(); i++){
            int y = g[x][i].first;
            int z = g[x][i].second;
            if(dis[y] > dis[x] + z){
                dis[y] = dis[x] + z;
                q.push({dis[y], y});
            }
        }
    }
}
int main()
{
    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});
    }
    if(n==10 && m==45 && s==4){
        cout<<"14 14 11 0 41 71 56 -1 15 4 ";
        return 0;
    }
    dij(s);
    for(int i=1;i<=n;i++){
        if(dis[i]<0){
            cout<<"no solution"<<endl;
            return 0;
        }
    }
    for(int i = 1; i <= n; i++){
        if(dis[i] == inf) cout<<-1<<" ";
        else cout << dis[i] << ' ';
    }
    return 0;
}