Submission

Score: 90

User: erng

Problemset: Fast Delivery

Language: cpp

Time: 0.020 second

Submitted On: 2026-03-16 14:08:03

#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
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, -1});
    for (int i=1; i<=n; i++) length[i]=4e18;
    length[st]=0;
    while (!pq.empty())
    {
        auto [cl, now, from]=pq.top();
        pq.pop();
        if (cl>=length[now] && now!=st) continue;
        length[now]=cl;
        if (from!=-1) back[now]=from;
        for (auto [w, to] : adj[now])
        {
            if (cl+w>length[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]==4e18)
        {
            cout<<" (inf)"<<'\n';
            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';
    }
}