Submission

Score: 0

User: syndrxme

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-14 15:51:28

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int, int>>> adj(n);
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v, w});
    }
    int startnode = 0;
    cin>>startnode;
    vector<int> dist(n,1e9);
    vector<int> parent(n,-1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[startnode] = 0;
    pq.push({0,startnode});
    while(!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(d>dist[u]) continue;
        for(auto edge:adj[u]){
            int v = edge.first;
            int w = edge.second;
            if(dist[u]+w<dist[v]){
                dist[v] = dist[u]+w;
                parent[v] = u;
                pq.push({dist[v],v});
            }
        }
    }

    for(int i=0;i<n;i++){
        if(i==startnode) continue;
        cout<<startnode<<"->"<<i<<" ";
        if(dist[i]==1e9){
            cout<<"(inf)\n";
        }else{
            cout << "(" << dist[i] << ") ";
        }
        vector<int> path;
        int curr = i;
        while(curr!=-1){
            path.push_back(curr);
            curr = parent[curr];
        }
        reverse(path.begin(),path.end());
        for(int node : path){
            cout << node << " ";
        }
        cout << "\n";
    }
    return 0;
}