Submission

Score: 100

User: theem1502

Problemset: Fast Delivery

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-24 23:05:15

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
    int v, e;
    cin >> v >> e;
    vector<vector<pair<int,int>>> adjlist(v);
    for (int i = 0; i < e; i++) {
        int first, second, third;
        cin >> first >> second >> third;
        adjlist[first].push_back(make_pair(second, third));
      //  adjlist[second].push_back((make_pair(first, third)));
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> theq;
    int start;
    cin >> start;
    theq.push(make_pair(0, start));
    vector<int> dist(v, INF);
    dist[start] = 0;
    vector<int> parent(v,-1);
    parent[start] = start;
    while(!theq.empty()) {
        int currentw = theq.top().first, currentv = theq.top().second;
        theq.pop();
        if (currentw > dist[currentv]) {
            continue;
        }
        for (auto [x, y] : adjlist[currentv]) {
            if (y + currentw < dist[x]) {
                dist[x] = y + currentw;
                theq.push({dist[x], x});
                parent[x] = currentv;
            }
        }

    }
/*
    for (int i = 0; i < v; i++) {
        cout << dist[i] << " ";
    }
    cout << "\n";
*/
    for (int i = 0; i < v; i++) {
        if (i == start) {
            continue;
        }
        if (dist[i] == INF) {
             cout << start << " -> " << i << " " << '(' << "inf" << ')' << " " << "\n";
             continue;
        }
        else {
        cout << start << " -> " << i << " " << '(' << dist[i] << ')' << " ";
        }
        vector<int> temp;
        int theparent = parent[i];
        temp.push_back(i);
        while(theparent != start) {
            temp.push_back(theparent);
            theparent = parent[theparent];
        }
        temp.push_back(start);
        reverse(temp.begin(), temp.end());
        for (int j = 0; j < temp.size(); j++) {
            cout << temp[j] << " ";
        }
        cout << "\n";

    }


}