Submission

Score: 90

User: C12

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-07 11:53:35

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define ll long long
#define ull unsigned long long
#define mp make_pair
 
#define mpiiii(a,b,c) make_pair(a,make_pair(b,c));
// ll mod = 1000000007;

void solve(){

    ll n,m;

    cin >> n >> m;

    vector<ll>out(n, LLONG_MAX);
    vector<ll>last(n, -1);
    vector<pii>adj[n];

    ll start,end,cost,path_start;

    while(m--){
        cin >> start >> end >> cost;
        adj[start].push_back(mp(end,cost));
    }

    cin >> path_start;

    priority_queue<piii,vector<piii>,greater<piii>>pq;
    pq.push(mp(0LL,mp(path_start,-1LL)));

    ll cnt = n;
    ll l;

    while(cnt > 0 && !pq.empty()){
        start = pq.top().s.f;
        cost = pq.top().f;
        l = pq.top().s.s;
        pq.pop();

        if(out[start] < LLONG_MAX) continue;
        out[start] = cost;
        last[start] = l;
        cnt--;
        for(auto x:adj[start]){

            if(x.f == path_start) continue;
            pq.push(mp(cost + x.s,mp(x.f,start)));
        }
    }

    stack<ll>st;

    for(int i = 0;i < n;i++){
        if(i == path_start) continue;
        cout << path_start << " -> " << i << " (";
        if(out[i] == LLONG_MAX){
            cout << "inf";
        }
        else{
            cout << out[i];
        }
        cout << ')';
        l = last[i];

        if(out[i] != LLONG_MAX){
            while(l != -1){
                st.push(l);
                l = last[l];
            }
            while (!st.empty())
            {
                cout << ' ' << st.top();
                st.pop();
            }
            cout << ' ' << i;
        }
        cout << '\n';
    }

    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
 
    // cin >> q;

    // while(q--)
        solve(); 

    return 0;
}
/*
6 8
0 2 1
1 0 3
1 2 5
2 3 2
2 4 4
3 0 5
3 5 5
4 5 1 
1

6 8
0 2 1
1 0 3
1 2
5
2 3 2
2 4 4
3 0 5
3 5 5
4 5 1 
0
*/