//
// Created by grtsinry43 on 5/8/25.
//

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
    int to, weight;
};

void dijkstra(int source, const vector<vector<Edge> > &graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX); // 存储最短路径长度
    vector<int> prev(n, -1); // 存储路径
    dist[source] = 0;

    // 优先队列，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
    pq.push({0, source});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto &edge: graph[u]) {
            int v = edge.to, weight = edge.weight;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INT_MAX) {
            cout << "Node " << i << " is unreachable from source " << source << ".\n";
        } else {
            cout << "Shortest distance to node " << i << " is " << dist[i] << ". Path: ";
            vector<int> path;
            for (int at = i; at != -1; at = prev[at]) {
                path.push_back(at);
            }
            ranges::reverse(path.begin(), path.end());
            for (int j = 0; j < path.size(); ++j) {
                cout << path[j] << (j + 1 < path.size() ? " -> " : "\n");
            }
        }
    }
}

int problem_1() {
    int n = 5; // 节点数
    vector<vector<Edge> > graph(n);

    // 添加边 (示例)
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 7});
    graph[2].push_back({4, 3});
    graph[3].push_back({4, 1});

    int source = 0; // 源点
    dijkstra(source, graph);

    return 0;
}