Submission

Score: 90

User: onlyme910

Problemset: Fast Delivery

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-18 10:08:26

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

priority_queue<pair<ll,int>> pq; //weight,note
vector<list<pair<int,ll>>> edge(200005); //note,weight
vector<ll> shortest(200005,LLONG_MAX);
vector<int> way(200005);

int main(){
    int n,m,st;
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        way[i] = i;
    }
    for(int i =0;i<m;i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        edge[a].push_back({b,c});
        //edge[b].push_back({a,c});
    }
    cin >> st;

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

    while (!pq.empty())
    {
        int n = pq.top().second;//note
        ll w = pq.top().first;//weight
        pq.pop();

        if(shortest[n] < w)continue;

        for(auto const& [ver,ww] : edge[n]){//weight2,note_end
            if(shortest[ver] > ww+w){
                shortest[ver] = ww+w;
                pq.push({ww+w,ver});
                way[ver] = n;
            }
        }
    }
    for(int i =0;i< n;i++){
        if(st == i)continue;
        else{
            stack<int> path;
            path.push(way[i]);
            while(path.top()!= st && path.top() != i){
                path.push(way[path.top()]);
            }
            if(shortest[i] == LLONG_MAX){
                cout << st << " -> " << i << " (inf)" << endl;
                continue;
            }
            else{
                cout << st << " -> " << i << " (" << shortest[i] << ") ";
            }
            while(!path.empty()){
                cout << path.top() << " ";
                path.pop();
            }
            cout << i << endl;
        }
    }
}