Submission

PPPPPPPPPP

Score: 100

User: MiyaZaki1072

Problemset: Fast Delivery

Language: cpp

Time: 0.004 second

Submitted On: 2025-04-18 15:22:23

#include <bits/stdc++.h>
using namespace std;
struct A{
    int v,w;
    bool operator<(const A&o)const{
        return w>o.w;
    }
};
vector<A>adj[100100];
priority_queue<A>pq;
int pre[100100];
int dis[100100];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    memset(pre,-1,sizeof pre);
    memset(dis,0x3f,sizeof dis);
    int n,m;cin>>n>>m;
    while(m--){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v,w});
    }
    int st;cin>>st;
    dis[st]=0;
    pq.push({st,0});
    while(pq.size()){
        A u = pq.top();pq.pop();
        for(auto &x:adj[u.v]){
            if(dis[x.v] > dis[u.v] + x.w){
                dis[x.v] = dis[u.v]+x.w;
                pre[x.v] = u.v;
                pq.push({x.v,dis[x.v]});
            }
        }
    }
    for(int i=0;i<n;i++){
        if(i==st)continue;
        cout<<st<<" -> "<<i<<" ";
        if(dis[i] > 1e9)cout<<"(inf)\n";
        else{
            cout<<"("<<dis[i]<<") ";
            stack<int>path;
            int ss = i;
            while(ss!=-1){
                path.push(ss);
                ss=pre[ss];
            }
            while(path.size()){
                cout<<path.top()<<" ";
                path.pop();
            }
            cout<<"\n";
        }
    }
}