Submission

Score: 80

User: Test

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-20 16:57:13

//16.26 - 16.55 29min
#include <bits/stdc++.h>
using namespace std;
int INF = 1e9;

void printPath(int v, vector<int>& parent) {
    if (v == -1) return;
    printPath(parent[v], parent);
    cout << v << " ";
    //if (parent[v] != -1) cout << " ";
}

int main(){
    int n,e;
    cin >> n >> e;
    vector<vector<pair<int,int>>> adj(n);
    for(int i=0;i<e;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        //adj[v].push_back({u,w});
    }
    int st;
    cin >> st;
    vector<int> dist(n,INF);
    vector<int> parent(n, -1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[st]=0;
    pq.push({0,st});

    while(!pq.empty()){
        auto[du,u]=pq.top(); //**
        pq.pop();

        if(du!=dist[u]) continue;

        for(auto &[v,w]:adj[u]){  // u->v w **
            if(du+w<dist[v]){
                dist[v]=du+w;
                parent[v] = u;
                pq.push({dist[v],v});
            }
        }
    }

    for(int i=0;i<n;i++){
        if(dist[i]==INF) cout << st << " -> " << i << " (INF)\n";
        else if(i==st) continue;
        else{
            cout << st << " -> " << i << " (" << dist[i] << ") ";
            printPath(i, parent);
            cout << "\n";
        }

    }
}