Submission

Score: 100

User: SayRo

Problemset: Fast Delivery

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-05 10:53:13

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n,m,start;
    cin>>n>>m;
    vector<int> dist(n,INT_MAX);
    vector<int> pa(n);
    vector<vector<pair<int,int>>> adj(n);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        adj[x].push_back({z,y});
    }
    cin>>start;
    dist[start]=0;
    pq.push({0,start});
    while(!pq.empty()){
        auto [w,u] = pq.top();
        pq.pop();
        if(w>dist[u]) continue;
        for(auto [ww,v] : adj[u]){
            if(w+ww<dist[v]){
                dist[v]=w+ww;
                pa[v]=u;
                pq.push({dist[v],v});
            }
        }
    }
    for(int i=0;i<n;i++){
        if(i==start) continue;
        cout<<start<<" -> "<<i<<" (";
        if(dist[i]==INT_MAX){cout<<"inf)\n";continue;}
        cout<<dist[i]<<") ";
        vector<int> path;
        for(int j=i;j!=start;j=pa[j]) path.push_back(j);
        path.push_back(start);
        reverse(path.begin(),path.end());
        for(auto x : path) cout<<x<<" ";
        cout<<endl;
    }
}