Submission

Score: 100

User: Kittiponn

Problemset: Fast Delivery

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-04 08:37:52

#include <bits/stdc++.h>
#define ll long long
#define sp << ' ' <<
#define nl << '\n' 
#define cnl cout << '\n'
using namespace std;
const int nx = 2e5+5;
const int INF = 1e9+5;
const int MOD = 1e9+7;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
vector<pair<ll,ll>> mp[nx];
ll n,m,en;
vector<ll> dis(nx,LLONG_MAX),back(nx);


int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        mp[a].push_back({b,c});
    }
    cin >> en;
    dis[en] = 0;
    pq.push({0,en});
    while(!pq.empty()){
        auto [w,c] = pq.top();
        pq.pop();
        if(dis[c] < w)continue;
        for(auto [nc,nw] : mp[c]){
            if(w+nw < dis[nc]){
                dis[nc] = w+nw;
                pq.push({dis[nc],nc});
                back[nc] = c;
            }
        }
    }
    for(int i = 0;i < n;i++){
        if(i == en)continue;
        if(dis[i] == LLONG_MAX) cout << en << " -> " << i << " (inf)\n";
        else {cout << en << " -> " << i << " (" << dis[i] << ") ";
        int idx = i;
        vector<int> ans;
        while(idx != en){
            ans.push_back(back[idx]);
            idx = back[idx];
        }
        reverse(ans.begin(),ans.end());
        ans.push_back(i);
        for(auto x : ans)cout << x << ' ';
        cnl;
        }
    }
}