Submission

PPPPPPPPPP

Score: 100

User: qwerty

Problemset: Fast Delivery

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-14 21:39:41

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

int dijkstraa(vector<vector<pair<int, int>>> &path, vector<vector<int>> &ans, int sor, int des) {
    int n = path.size();
    vector<int> parent(n, -1);
    vector<int> curr;
    vector<int> dis(n, INT_MAX);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dis[sor] = 0;
    pq.push({0, sor});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;

        for (auto i : path[u]) {
            int v = i.first;
            int w = i.second;
            if (!visited[v] && dis[v]>dis[u]+w) {
                dis[v] = dis[u]+w;
                parent[v] = u;
                pq.push({dis[v], v});
            }
        }
    }
    if (dis[des] == INT_MAX) return -1;

    for (int v = des ; v!=-1 ; v = parent[v]) {
        curr.push_back(v);
    }
    reverse(curr.begin(), curr.end());
    ans.push_back(curr);
    return dis[des];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> path(n);
    for (int i = 0 ; i < m ; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        path[u].push_back({v, w});
    }
    int sor;
    cin >> sor;

    vector<vector<int>> ans(n);
    for (int i = 0 ; i < n ; i++) {
        if (sor!=i) {
            int dis = dijkstraa(path, ans, sor, i);
            if (dis == -1) {
                cout << sor << " -> " << i << " (inf) ";
            } else {
                cout << sor << " -> " << i << " (" << dis << ") ";
                for (auto j : ans.back()) {
                    cout << j << " ";
                }
            }
            cout << endl;
        }
    }
}