Submission

Score: 90

User: sorrkub

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-11 19:06:50

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<long long ,long long> pll; typedef pair<long long, pair<long long , long long >> plpll;
const int inf = 1e9+7;
int dx[8] = {0,0,-1,1,-1,1,-1,1} , dy[8] = {1,-1,0,0,1,-1,1,-1};
#define F first
#define S second
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<pll>> adj(n);
    vector<int> parent(n);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    int str;
    cin>>str ;
    vector<int> dis(n,inf);
    vector<bool> vis(n,false);
    dis[str] = 0;
    parent[str] = -1;

    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,str});
    
    int cnt =0 ; 
    while(!pq.empty()){
        auto [w,x] = pq.top();
        pq.pop();
        // if(cnt == n){
        //     break;
        // }   
        if(vis[x]){
            continue;
        }
        vis[x] = true;

        for(auto [go,ww] : adj[x]){
            if(dis[go] == inf){
                cnt++;
            }
            if(w+ww <  dis[go]){
                dis[go] = w+ww;
                pq.push({dis[go],go});
                parent[go] = x; 
            }
        }
    }
    for(int i=0;i<n;i++){
        if(i!=str){
            if(dis[i] == inf){
                cout<<str<<" -> "<<i<<" "<<"("<<"inf"<<")\n";
                continue;
            }
            cout<<str<<" -> "<<i<<" "<<"("<<dis[i]<<") ";
            int j = i;
            vector<int> temp;
            string b;
            while(1){
                if(j==-1){
                    break;
                }
                // temp.push_back(j);
                // j = parent[j];
                b = char(j + '0') + b;
                j=parent[j];
            }  
            for(int i=0;i<b.size();i++){
                cout<<b[i]<<" ";
            } 
            // for(int p = temp.size()-1;p>=0;p--){
            //     cout<<p<<" ";
            // }
             cout<<"\n";
        }

       
    }
}

signed main(){
    FAST_IO
    int q=1;
    //cin>>q;
    while(q--){
        solve();
    }
    return 0;
}

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \|     |//  `.
            /  \|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
              pass System Test!
*/