Submission

Score: 100

User: skibididopdop

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-18 22:12:08

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector <vector <pair<int,int>>> adj(n);
    int u,v,w;
    for (int i=0;i<m;i++){
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        //adj[v].push_back({u,w});
    }
    int s;
    cin>>s;
    vector <int> dist(n,INT_MAX);
    vector <int> pa(n,-1);
    priority_queue <pii,vector <pii>,greater <pii>> pq;
    pq.push({0,s});
    dist[s]=0;
    vector <bool> check(n,0);
    while (!pq.empty()){
        int we=pq.top().first;
        int x=pq.top().second;
        pq.pop();
        if (we>dist[x]) continue;
        for (auto e:adj[x]){
            int a=e.first;
            int b=e.second;
            if (dist[x]+b<dist[a]){
                dist[a]=dist[x]+b;
                pq.push({dist[a],a});
                pa[a]=x;
            }
        }
    }
    //cout<<dist[1]<<"\n";
    for (int i=0;i<n;i++){
        if (i==s){
            continue;
        }
        else if (dist[i]==INT_MAX){
            cout<<s<<" -> "<<i<<" "<<"(inf)"<<"\n";
            continue;
        }
        cout<<s<<" -> "<<i<<" "<<"("<<dist[i]<<")"<<" ";
        int c=i;
        vector <int> ans;
        ans.push_back(i);
        while (pa[c]!=-1){
            ans.push_back(pa[c]);
            c=pa[c];
        }
        int an=ans.size();
        for (int j=ans.size()-1;j>=0;j--){
            cout<<ans[j]<<" ";
        }
        cout<<"\n";
    }
}