Submission

Score: 100

User: august

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-22 14:32:53

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

#define int long long
#define pi pair<int,int>

const int INF = 1e18;

void fnd(int u, int tar, vector<int> &par) {
    if (u==tar) {
        cout<< tar<< ' ';
        return;
    }

    fnd(par[u], tar, par);
    cout<< u<< ' ';
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int n,m;
    cin>> n>> m;

    vector<vector<pi>> g(n);
    for (int i=0; i<m; i++) {
        int u,v,w;
        cin>> u>> v>> w;
        g[u].push_back({v,w});
    }

    int st;
    cin>> st;

    vector<int> dist(n, INF), par(n);
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    iota(par.begin(), par.end(), 0);

    pq.push({0 ,st});
    dist[st] = 0;
    
    while (!pq.empty()) {
        pi cur = pq.top(); pq.pop();
        int d=cur.first, u=cur.second;

        if (d > dist[u]) continue;

        for (auto &x : g[u]) {
            int v = x.first, w=x.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                par[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i=0; i<n; i++) {
        if (i==st) continue;

        cout<< st<< " -> "<< i<<  " (";
        if (dist[i]==INF) cout<<"inf";
        else cout<< dist[i];
        cout<< ") ";

        if (dist[i] != INF) fnd(i, st, par);
        cout<< '\n';
    }
}