Submission

Score: 100

User: mantaggez

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-23 17:42:45

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int INF = 1e9;

int n, m, src;
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    const int nx = n + 5;
    vector<int> dist(nx, INF), pa(nx, -1);
    vector<pii> adj[nx];
    for(int i=0;i<m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    cin >> src;
    dist[src] = 0;
    pq.push({0, src});
    while(!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if(w > dist[u]) continue;
        for(auto [v, nw] : adj[u]) {
            if(dist[v] > w + nw) {
                pa[v] = u;
                dist[v] = w + nw;
                pq.push({dist[v], v});
            }
        }
    }

    for(int i=0;i<n;i++) {
        if(i == src) continue;
        cout << src << " -> " << i << " (";
        if(dist[i] == INF) {
            cout << "inf) " << '\n';
            continue;
        }
        else cout << dist[i] << ") ";

        vector<int> path;
        for(int v=i;v!=-1;v=pa[v]) {
            path.push_back(v);
        }
        reverse(path.begin(), path.end());
        for(int it : path) cout << it << ' ';
        cout << '\n';
    }

    return 0;
}