Submission

Score: 100

User: Trees

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-04 09:16:37

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

    int h;
    vector<int> c;

void ant(int cont,stack<int> l)
{
    queue<int> q;
    q.push(cont);
    l.push(cont);

    while(!q.empty()){
        int a = q.front();
        q.pop();
        if(a == c[a])break;
        l.push(c[a]);
        q.push(c[a]);
    }

    while(!l.empty()){
        int a = l.top();
        l.pop();
        cout << a << ' ';
    }

}

int main()
{
    int x,y;
    cin >> x >> y;
    vector<vector<bool>> a(x,vector<bool>(x,false));
    vector<vector<int>> b(x,vector<int>(x,2e9));

    for(int i=0;i<y;++i){
        int aa,bb,num;
        cin >> aa >> bb >> num;
        b[aa][bb] = min(num,b[aa][bb]);
        a[aa][bb] = true;
    }

    c.resize(x);
    vector<int> cont(x,2e9);

    cin >> h;

    c[h] = h;
    cont[h] = 0;

    queue<int> q;
    q.push(h);

    while(!q.empty()){
        int aa = q.front();
        q.pop();

        for(int i=0;i<x;++i){
            if(a[aa][i]){
                if(cont[aa]+b[aa][i] < cont[i]){
                    cont[i] = cont[aa]+b[aa][i];
                    c[i] = aa;
                    q.push(i);
                }
            }
        }
    }

    for(int i=0;i<x;++i){
        if(i == h)continue;
        stack<int> l;
        bool kk = true;
        cout << h << " -> " << i << " (";
        if(cont[i] == 2e9){cout << "inf)" << endl;kk=false;}
        else cout << cont[i];
        if(kk){
        cout << ") ";
        ant(c[i],l);
        cout << i << endl;
        }
    }


}