Submission

PPPPPPPPPP

Score: 100

User: Nathlol2

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-15 15:01:29

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define INF 2e9
using namespace std;

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<pii>> g(n);
    int a, b, c;
    for(int i = 0;i<m;i++){
        cin >> a >> b >> c;
        g[a].pb({b, c});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<int> dist(n, INF);
    vector<int> p(n, -1);
    int s;
    cin >> s;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if(d > dist[u]){
            continue;
        }
        for(auto [v, w] : g[u]){
            if(d + w < dist[v]){
                dist[v] = d + w;
                pq.push({d + w, v});
                p[v] = u;
            }
        }
    }
    for(int i = 0;i<n;i++){
        if(i == s){
            continue;
        }
        if(dist[i] == INF){
            cout << s << " -> " << i << " (inf)\n";
            continue;
        }
        cout << s << " -> " << i << " (" << dist[i] << ")" << " ";
        vector<int> path;
        int j = i;
        while(p[j] != -1){
            path.pb(j);
            j = p[j];
        }
        path.pb(s);
        reverse(path.begin(), path.end());
        for(auto x : path){
            cout << x << " ";
        }
        cout << '\n';
    }
}