Submission

Score: 40

User: Neozaawwman1

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 13:07:21

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
int n,m,str;
vector<list<pair<int,ll>>> ed;//v,ww
ll dist[100005];
int pa[100005];
priority_queue<pair<ll,int>> pq;//-w,u
stack<int> s;
void printPa(int a){
    if(pa[a]==-1){
        s.push(a);
        return;
    }
    s.push(a);
    return printPa(pa[a]);
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    ed.resize(n);
    for(int i=0; i<n; i++){
        pa[i]=i;
    }
    for(int i=0;i<n;i++){
        dist[i] = INF;
    }
    for(int i=0; i<m; i++){
        int a,b;cin>>a>>b;
        ll c;cin>>c;
        ed[a].push_back({b,c});
        ed[b].push_back({a,c});
    }
    cin>>str;
    pa[str]=-1;
    dist[str]=0;
    pq.push({0,str});
    while(!pq.empty()){
        ll w = -1*(pq.top().first);
        int u =pq.top().second;
        pq.pop();
        if(dist[u]<w)continue;
        for(auto xx:ed[u]){
            int v = xx.first;
            ll ww = xx.second;
            if(dist[v]>ww+w){
                dist[v]=w+ww;
                pa[v]=u;
                pq.push({-(ww+w),v});
            }
        }
    }
    for(int i=0; i<n; i++){
        if(i==str)continue;
        if(dist[i]==INF){
            cout<<str<<' '<<"->"<<' '<<i<<' '<<'('<<"inf"<<')'<<endl;
        }
        cout<<str<<' '<<"->"<<' '<<i<<' '<<'('<<dist[i]<<')'<<' ';
        printPa(i);
        while(!s.empty()){
            cout<<s.top()<<' ';
            s.pop();
        }
        cout<<endl;
    }
    return 0;
}