Submission

Score: 100

User: havename

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-04 09:45:49

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

const int inf=1e9+7;

int main(){
    int n,m,st;
    cin>>n>>m;

    vector<int> dit(n+1,inf);
    vector<vector<pair<int,int>>> adj(n+1);
    vector<vector<int>> prt(n);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    for (int i = 0; i < n; ++i) prt[i].emplace_back(i);  
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;

    cin>>st;

    dit[st]=0;
    pq.push({0,st});

    while(!pq.empty()){
        int w=pq.top().first;
        int v=pq.top().second;
        pq.pop();

        if(dit[v]<w) continue;

        for(auto &[b,d] : adj[v]){
            if(dit[b]>d+w){
                dit[b]=d+w;
                prt[b]=prt[v];
                prt[b].emplace_back(b);
                pq.push({dit[b],b});
            }
        }
    }

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

        cout << st << " -> " << i << " (";
        if(dit[i]==inf) cout << "inf)\n";
        else{ 
            cout << dit[i] << ") ";
            //cout << " : ";

            for(auto x : prt[i]){
                cout << x << " ";
            }

            cout << "\n";
        }
    }
}