Submission

Score: 80

User: faofao

Problemset: Fast Delivery

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-14 14:01:00

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 200005 ;
int n ,m ;

vector<vector<pair<int,ll>>> path(mxN) ;
int pa[mxN] ;
ll dist[mxN] ;

void bfs(int st){
    priority_queue<pair<ll,int>> pq ;
    pq.push({0,st}) ;
    while(!pq.empty()){
        auto [w,u] = pq.top() ;
        pq.pop() ;
        w*=-1 ;

        if(dist[u] < w) continue;
        // dist[u] = w ;

        for(auto [v,ww] : path[u]){
            if(dist[v] < w+ww) continue;
            dist[v] = w+ww ;
            pa[v] = u;
            pq.push({-1*(w+ww),v}) ;
        }
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0) ;
    cin >> n >> m ;
    memset(dist, 0x3f , sizeof(dist)) ;
    for(int i=0 ; i<n ; i++) pa[i] = i ;
    for(int i=0 ; i<m ; i++){
        int u,v;
        ll w;
        cin >> u >> v >> w ;
        pa[v] = u ;
        path[u].push_back({v,w}) ;
    }
    int x ; cin >> x; //first town
    pa[x] = -1 ;
    dist[x] = 0 ;
    bfs(x) ;

    for(int i=0 ; i<n ; i++){
        if(i==x) continue;
        cout << x <<" -> "<< i << " (";
        
        if(dist[i] > 1e18){
            cout << "inf)\n" ;
            continue;
        }
        cout << dist[i] << ") " ;
        int tmp = i ;
        stack<int> s;
        cout << x << " ";
        while(tmp!=x){
            s.push(tmp) ;
            tmp = pa[tmp] ;
        }
        while(!s.empty()){
            cout << s.top() << " " ;
            s.pop() ;
        }
        cout << "\n" ;
    }
}