Submission

Score: 0

User: nik121416

Problemset: Fast Delivery

Language: cpp

Time: 0.174 second

Submitted On: 2026-03-18 13:14:56

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

void f(int root,int cur,int node,vector<vector<int>> &ans,vector<int> &edge){
    if(cur == root){
        //ans[node].push_back(root);
        //ans[node].push_back(node);
        return;
    }
    ans[node].push_back(edge[cur]);
    f(root,edge[cur],node,ans,edge);
}
const int inf = 1e9+7;

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0;i < m;i++){
        int a,b,w;
        cin >> a >> b >> w;
        adj[a].push_back({w,b});
    }
    int s;
    cin >> s;
    priority_queue<pair<int,int>, vector<pair<int,int>> ,greater<pair<int,int>>> pq;
    vector<int> dis(n,inf);
    pq.push({0,s});
    dis[s] = 0;
    vector<int> edge(n);
    edge[s] = s;
    //vector<bool>vis(n,false);
    while(!pq.empty()){
        int w = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        int mn;
        // if(!vis[u]){
        //     cout << u <<' ';
        //     vis[u] = true;
        // }
        for(auto [ww,v]:adj[u]){
            if(ww + w < dis[v]){
                dis[v] = ww + w;
                edge[v] = u;
                pq.push({ww+w,v});
                mn = v;
            }
        }
    }
    // for(int i:dis){
    //     cout << i << ' ';
    // }
    // cout << '\n';
    // for(auto i : adj){
    //    for(auto [w,j]:i){
    //     cout << '{' << w << ','<<  j << '}' << ' ';
    //    }
    //    cout << '\n';
    // }
    int root;
    for(int i = 0 ;i < n;i++){
        if(i == edge[i]){
            root = i;
            break;
        }
    }
    // cout << root;
    vector<vector<int>> ans(n);
    
    for(int i = 0 ; i < n;i++){
        if(i == root) continue;
        f(root,i,i,ans,edge);
    }
    for(int i = 0 ; i < n;i++){
        if(i == s) continue;
        reverse(ans[i].begin(),ans[i].end());
        cout << s <<" -> " <<i;
        if(dis[i] == inf){
            cout << "(inf) " << '\n';
            continue;
        }
        else{
            cout << ' ' << '(' << dis[i] << ')';
        }
        
        for(int j : ans[i]){
            cout << j << ' ';
        }
        cout << i << ' ';
        cout << '\n';
    }
}