Submission

PPPPPPPPPP

Score: 100

User: Nakornrat

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-28 22:23:19

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long int;
using pli = pair<ll, int>;
vector<vector<pli>> gh;
const ll inf = 1e12+10;
int n, m;
vector<ll> dist;
vector<int> par;
void dijkstra(int st){
    priority_queue<pli, vector<pli>, greater<pli>> q;
    par[st] = -1;dist[st] = 0;
    q.push({0, st});
    while(!q.empty()){
        int un = q.top().second;
        ll uw = q.top().first;
        q.pop();
        if(uw>dist[un])continue;
        // cout<<un<<endl;
        for(auto [vn, vw]:gh[un]){
            // cout<<vn<<endl;
            ll w = vw+dist[un];
            if(w<dist[vn]){
                dist[vn] = w;
                q.push({w, vn});
                par[vn] = un;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    gh.resize(n);
    par.resize(n, -1);
    dist.resize(n, inf);
    while(m--){
        int x, y, w;cin>>x>>y>>w;
        gh[x].push_back({y, w});
        // gh[y].push_back({x, w});
    }
    int st;cin>>st;
    dijkstra(st);
    vector<vector<int>> ans;
    for(int i = 0;i<n;i++){
        if(i==st)continue;
        vector<int> temp;
        int k =i;
        while(k!=-1){
        temp.push_back(k);
        k = par[k];
    }
    reverse(temp.begin(), temp.end());
    ans.push_back(temp);
}
    int i = 0;
    for(auto x:ans){
        if(i==st)++i;
        cout<<st<<" -> "<<i<<" (";
        if(dist[i]==inf){
            cout<<"inf)"<<endl;
            ++i;
            continue;
        }
        cout<<dist[i]<<") ";
        ++i;
        for(auto y:x){
            cout<<y<<' ';
        }
        cout<<endl;
    }
}