Submission

PPPPPPPPPP

Score: 100

User: krittaphot

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-15 13:55:38

#include <bits/stdc++.h>

using namespace std;

void solve(vector<vector<pair<int,int>>> &adj,int start,int n){
    priority_queue<pair<int,int> ,vector<pair<int,int>>,greater<>> pq;
    vector<int> parent(n,-1);
    vector<int> dist(n,INT_MAX);

    pq.push({0,start});
    dist[start] = 0;
    while(!pq.empty())
    {
        int w = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(w > dist[node]) continue;

        for(auto &i : adj[node])
        {
            int next = i.first;
            int cost = i.second;

            if(w+cost < dist[next]){
                pq.push({w+cost,next});
                dist[next] = w+cost;
                parent[next] = node;
            }
        }
    }

    for(int i = 0;i<n;i++){
        if(i == start) continue;

        if(dist[i] == INT_MAX){
            cout << start << " -> " << i << " " << "(inf)" << "\n";
        }
        else{
            cout << start << " -> " << i << " (" << dist[i] << ") ";
            vector<int> path;
            for(int j = i;parent[j]!=-1;j = parent[j]){
                path.push_back(j);
            }
            reverse(path.begin(),path.end());
            cout << start << " ";
            for (int city : path) cout << city << " ";
            cout << "\n";
        }
        
    }
    

}

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({b,w});
    }

    int start;
    cin >> start;

    solve(adj,start,n);
}