Submission

PPPPPPPPPP

Score: 100

User: Nightingale

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-31 12:20:58

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

int a, b;
map<int, vector<int>> path;
map<int, int> preve;

void star(vector<vector<int>> &dp, int start, vector<int> &meta) {
    queue<int> q;
    q.push(start);
    meta[start] = 0;

    while (!q.empty()) {
        int here = q.front();
        q.pop();

        for (int next : path[here]) {
            if (dp[here][next] != LLONG_MAX && meta[here] != LLONG_MAX &&
                meta[here] + dp[here][next] < meta[next]) {
                meta[next] = meta[here] + dp[here][next];
                preve[next] = here;
                q.push(next); // Push to queue to ensure correct order
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b;
    vector<vector<int>> dp(a, vector<int>(a, LLONG_MAX));
    vector<int> meta(a, LLONG_MAX);

    for (int i = 0; i < b; i++) {
        int c, d, e;
        cin >> c >> d >> e;
        dp[c][d] = e;
        path[c].push_back(d);
    }

    int want;
    cin >> want;

    star(dp, want, meta);

    for (auto it = path.begin(); it != path.end(); it++) {
        if (it->first != want) {
            if (meta[it->first] == LLONG_MAX) {
                cout << want << " -> " << it->first << " (" << "inf" << ") ";
            } else {
                cout << want << " -> " << it->first << " (" << meta[it->first] << ") ";
                int meat = it->first;
                vector<int> walker;
                walker.push_back(meat);

                while (meat != want) {
                    meat = preve[meat];
                    walker.push_back(meat);
                }

                for (int i = walker.size() - 1; i >= 0; i--) {
                    cout << walker[i] << ' ';
                }
            }
            cout << '\n';
        }
    }
}