题目背景
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
说明/提示
样例解释请参考 数据随机的模板题。
\(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\)。
本题数据可能会持续更新，但不会重测，望周知。
题解
- Dijkstra 算法（适用于非负权图）
- 使用优先队列优化：每次插入和更新操作 \(O(log N)\)，总复杂度 \(O((N+E) log N)\) ，适合稀疏图。
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 100004;
const int maxm = 200005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int head[maxn], to[maxm], nxt[maxm], w[maxm];
ll Dist[maxn];struct node {int pos;ll dis;bool operator<(const node &T) const {return dis > T.dis; // 最小堆}
};priority_queue<node> Q;int main() {int n, m, s;cin >> n >> m >> s;for (int i = 1; i <= m; i++) {int x, y, z;scanf("%d%d%d", &x, &y, &z);to[i] = y;nxt[i] = head[x];head[x] = i;w[i] = z;}for (int i = 1; i <= n; i++) Dist[i] = INF;Dist[s] = 0;Q.push({s, 0});while (!Q.empty()) {node T = Q.top(); Q.pop();int u = T.pos;ll d = T.dis;if (d > Dist[u]) continue; // 过时节点跳过for (int e = head[u]; e != 0; e = nxt[e]) {int v = to[e];ll nd = d + w[e];if (nd < Dist[v]) {Dist[v] = nd;Q.push({v, nd});}}}for (int i = 1; i <= n; i++) {if (Dist[i] == INF) printf("INF ");else printf("%lld ", Dist[i]);}printf("\n");return 0;
}