洛谷P4779 【模板】单源最短路径（标准版）

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$100 \rightarrow 60$；

$\text{Ag} \rightarrow \text{Cu}$；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$。

第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

样例 #1

样例输入 #1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

样例输出 #1

0 2 4 3

提示

样例解释请参考 [数据随机的模板题](https://www.luogu.org/problemnew/show/P3371)。 。)

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq

题解

#include <bits/stdc++.h>
#define AC return 0
using namespace std;

struct edge {
    int v, w;
};
struct node {
    int dis, u;
    bool operator>(const node a) const {
        return dis > a.dis;
    }
};

int n, m, s, dis[100010], b[100010];
vector<edge> e[100010];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    q.push((node){0, s});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (b[u])
            continue;
        b[u] = 1;
        for (auto t : e[u]) { // 遍历某一容器中的所有元素的简便写法
            int v = t.v, w = t.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push((node){dis[v], v});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].push_back((edge){v, w});
    }
    dijkstra(n, s);
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    cout << endl; // For Debugging
    AC;
}