Dijkstra求无向图单源最短路径

#include <bits/stdc++.h>

using namespace std;
// 使用 long long 防止路径总长度超过 int 范围（约 20 亿）
using ll = long long;

// 定义一个极大的数表示“无穷大”。
// 0x3f3f3f3f3f3f3f3f 在 long long 下是一个非常大的数，
// 且两个这样的数相加一般不会溢出，非常适合做最短路的初始值。
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

// Edge 结构体有两个用途：
// 1. 在邻接表 adj 中：u 表示邻接点编号，w 表示边的权重。
// 2. 在优先队列 q 中：u 表示节点编号，w 表示从起点 s 到 u 的当前最短距离。
struct Edge {
    int u;
    ll w;

    // 重载小于号运算符，用于优先队列的排序。
    // C++ 的 priority_queue 默认是“大根堆”（最大值在堆顶）。
    // 我们需要“小根堆”（距离最小的在堆顶），所以这里逻辑反过来：
    // 如果当前 w 大于对方的 w，则认为优先级更低。
    bool operator< (const Edge& o) const {
        return w > o.w;
    }
};

int main() {
    // 关闭输入输出同步流，提高 cin/cout 的读写速度，防止 TLE（超时）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    cin >> n >> m >> s; // 输入点数 n，边数 m，起点 s

    // 邻接表存储图，adj[u] 存储的是从 u 出发的所有边
    vector<vector<Edge> > adj(n + 1);

    // 读入 m 条边
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        // 无向图，所以要双向建边
        adj[u].push_back({v, w}); // u -> v 权重 w
        adj[v].push_back({u, w}); // v -> u 权重 w
    }

    // 优先队列（小根堆），存储 pair {节点 u, 距离 w}
    // 堆顶永远是当前未确定的点中，距离起点最近的那个点
    priority_queue<Edge> q;

    // dist 数组：存储起点 s 到各个点的最短距离，初始化为无穷大
    vector<ll> dist(n + 1, inf);

    // vis 数组：标记某个点是否已经确定了最短路（是否被“出队”过）
    vector<bool> vis(n + 1, false);

    // 初始状态：起点 s 到自己的距离为 0
    q.push({s, 0});
    dist[s] = 0;

    // Dijkstra 主循环
    while (!q.empty()) {
        // 取出堆顶元素（当前距离起点最近的点）
        Edge now = q.top();
        q.pop();

        int u = now.u; // 当前节点编号

        // 如果该点已经被访问过（即已经确定了最短路），则跳过。
        // 这是因为同一个点可能多次入队（每次发现更短路径都会入队），
        // 只有第一次出队时的距离才是最短的。
        if (vis[u])
            continue;

        // 标记该点已确定最短路
        vis[u] = true;

        // 遍历 u 的所有邻接点（扫描出边）
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].u;    // 邻接点 v
            ll w = adj[u][i].w;     // 边 u-v 的权重

            // 松弛操作 (Relaxation)：
            // 如果经由 u 到达 v 的距离（dist[u] + w）比当前记录的 dist[v] 更短
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;  // 更新 v 的最短距离
                q.push({v, dist[v]});   // 将更新后的 v 放入队列，以便后续扩展
            }
        }
    }

    // 输出从起点 s 到所有点 1~n 的最短距离
    for (int i = 1; i <= n; ++i) {
        cout << dist[i] << " ";
    }
    cout << "\n";

    return 0;
}