Dijkstra

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

#define INF 1e9

using namespace std;

pair<vector<int>, vector<int>> dijkstra(vector<vector<pair<int, int>>> &graph, int source) {
    // Conains pairs of distance from source and the node itself
    // <type of data, container of data (we use vector of pairs), comparison operator(greater turns the priority queue into a min priority queue)>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
    queue.push({ 0, source }); // distance from source to source is zero

    // stores distance from source
    vector<int> distances(graph.size(), INF);
    distances[source] = 0; // distance from source to source is zero

    // Initialize with -1, indicating that we haven't found the optimal
    // parent node for every node
    vector<int> parents(graph.size(), -1);

    while (!queue.empty()) {
        // Pop the closest undiscovered node
        pair<int, int> current_node = queue.top();
        queue.pop();

        int dist = current_node.first;
        int node = current_node.second;

        // We do this to avoid processing stale distances.
        // Suppose, we push { 10, B } into the queue.
        // Before we reach this path, suppose we find a better path { 5, B } and push
        // it. As it is a min priority queue, { 5, B } will now be popped before { 10, B }.
        // Now, we can clearly see that there's a stale path { 10, B } we do not need to process. { 5, B } will set B's source distance to 5... which is less than 10. So, this check will skip the useless iteration over B's neighbors through the stale path.
        if (dist > distances[node]) continue;

        // Iterate over every neighbor of the node
        for (auto &edge: graph[node]) {
            int neighbor = edge.first;
            int distance = edge.second;

            // Check if distance from current node to this neighbor is smaller than what we recorded before... if smaller, we store the new path.
            int new_distance = dist + distance;
            if (new_distance < distances[neighbor]) {
                distances[neighbor] = new_distance;
                queue.push({ distances[neighbor], neighbor });

                // the current node to neighbor distance is the smallest, so we reach this neighbor by current node.
                parents[neighbor] = node;
            }
        }
    }

    return { distances, parents };
}

vector<int> construct_path(vector<int> &parents, int target) {
    vector<int> path;

    // We keep following the parent of target node and push
    // until we reach the source node(it's parent is -1)
    while (target != -1) {
        path.push_back(target);
        target = parents[target];
    }

    // The path is reversed as we started from the target node,
    // so we reverse the node.
    reverse(path.begin(), path.end());

    return path;
}

int main() {
    int nodes, edges, source;
    cin >> nodes >> edges >> source;

    vector<vector<pair<int, int>>> graph(nodes + 1);

    for (int i = 1; i <= edges; i++) {
        int from, to, dis;
        cin >> from >> to >> dis;

        graph[from].push_back({ to, dis });
    }

    // C++ syntax to destructure a pair, nothing too fancy
    auto [ distances, parents ] = dijkstra(graph, source);

    for (int i = 1; i <= nodes; i++) {
        if (parents[i] == -1 && i != source) {
            cout << i << "(INF)" << endl;
            continue;
        }
        vector<int> path = construct_path(parents, i);
        for (int j = 0; j < path.size() - 1; j++) {
            cout << path[j] << " -> ";
        }
        cout << i << "(" << distances[i] << ")" << endl;
    }

    return 0;
}