Submission

Score: 90

User: tHeNyXs

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-04 08:27:10

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<pair<int, int>> graph[n];
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }
    int start; cin >> start;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(start, 0);
    vector<int> dist(n, INT_MAX);
    vector<vector<int>> path(n);
    for (int i = 0; i < n; ++i) path[i].emplace_back(i);
    dist[start] = 0;
    while (!pq.empty()) {
        auto [u, uw] = pq.top(); pq.pop();

        if (uw > dist[u]) continue;

        for (auto[v, w] : graph[u]) {
            if (dist[v] <= dist[u]+w) continue;
            dist[v] = dist[u]+w;
            path[v] = path[u];
            path[v].emplace_back(v);
            pq.emplace(v, dist[v]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i == start) continue;
        cout << start << " -> " << i << " (";
        if (dist[i] == INT_MAX) cout << "inf)\n";
        else {
            cout << dist[i] << ") ";
            for (int j : path[i]) {
                cout << j << " ";
            }
            cout << '\n';
        }
    }

    return 0;
}