Submission

Score: 30

User: erng

Problemset: Fast Delivery

Language: cpp

Time: 0.018 second

Submitted On: 2026-03-06 10:30:00

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=1e6;

ll n, m, x, y, l, st, vs[nx], length[nx], ans[nx], tmp, back[nx];
vector<pair<ll,ll>> adj[nx];
priority_queue<tuple<ll,ll, ll>, vector<tuple<ll,ll, ll>>, greater<tuple<ll,ll, ll>>> pq; // length, now, from
stack<ll> s;

int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>x>>y>>l;
        x++;
        y++;
        adj[x].push_back({l, y});
        adj[y].push_back({l, x});
    }
    cin>>st;
    st++;
    pq.push({0, st, 0});
    while (!pq.empty())
    {
        auto [cl, now, prev]=pq.top();
        pq.pop();
        if (vs[now]) continue;
        if (prev!=0) back[now]=prev;
        if (now!=st) length[now]=cl;
        vs[now]=1;
        for (auto [w, to] : adj[now])
        {
            if (vs[to]) continue;
            else pq.push({cl+w, to, now});
            // cout<<"debug "<<cl+w<<' '<<to<<' '<<now<<'\n';
        }

    }
    for (int i=1; i<=n; i++)
    {
        if (i==st) continue;
        cout<<st-1<<" -> "<<i-1;
        if (length[i]==0)
        {
            cout<<"inf";
            continue;
        }
        cout<<" ("<<length[i]<<") ";
        // for (auto c : back[i]) cout<<c-1<<" ";
        ll c=i;
        s.push(i);
        while (back[c]!=0) 
        {
            // cout<<back[c]<<" ";
            s.push(back[c]);
            c=back[c];
        }
        while (!s.empty()) cout<<s.top()-1<<" ", s.pop();
        cout<<'\n';
    }
}