【模板】单源最短路径（标准版）
题目描述
给定一个 个点， 条 有向图，所有边权都为非负整数，请你计算从 出发，到每个点的距离。数据保证你能从 出发到任意点。
这里有三份模板供大家参考，请注意：
- 请大家务必自己写一遍，这是图论题里最常考的算法
- 以后大家的代码会越来越长，在第一次写的时候，一定要写规范，并且尽可能封装好，方便以后重复利用
（点击展开）二维vector+queue：类似 bfs，写法简单，但多数题目会 TLE，不推荐
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
// template 是 C++ 的模板方法, 方便我们封装代码
template <typename T>
struct Graph {
int n; // n: 点的个数, m: 边的个数
vector<vector<pair<int, int>>> g; // 二维 vector 存储图
vector<T> d; // d[i] 表示起点到 i 的最短距离
Graph(int n_): n(n_) {
g.resize(n + 1);
d.resize(n + 1); // resize() 也可只写长度, 不赋初值
}
void add_edge(int u, int v, int w) {
g[u].push_back({v, w});
}
void spfa(int s) {
// 求最短路, 将 d[i] 赋初值为无穷大
for (int i = 1; i <= n; i++) d[i] = inf;
queue<int> q;
q.push(s), d[s] = 0;
while (!q.empty()) {
auto u = q.front();
q.pop();
for (auto [v, w] : g[u]) {
T tmp = d[u] + w;
if (tmp < d[v]) q.push(v), d[v] = tmp;
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, s, u, v, w;
cin >> n >> m >> s;
Graph<int> G(n);
while (m--) {
cin >> u >> v >> w;
G.add_edge(u, v, w); // 有向图只添加 1 条边
// G.add_edge(v, u, w); // 无向图要添加 2 条边
}
G.spfa(s);
for (int i = 1; i <= n; i++) cout << G.d[i] << " \n"[i == n];
return 0;
}
（点击展开）链式前向星存储图+priority_queue 优化：跑的最快，推荐
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
// template 是 C++ 的模板方法, 方便我们封装代码
template <typename T>
struct Graph {
int n, m, e; // n: 点的个数, m: 边的个数, e: 已经插入的边的个数
vector<int> head, pnt, nxt; // 链式前向星存储图
vector<T> wv; // 边权
vector<T> d; // d[i] 表示起点到 i 的最短距离
Graph(int n_, int m_): n(n_), m(m_) {
e = 0;
// 依次对 vector 调整长度
// resize(n, -1): 表示将长度调整为 n, 并赋初值为 -1
head.resize(n + 1, -1);
pnt.resize(m, 0);
wv.resize(m, 0);
nxt.resize(m, 0);
d.resize(n + 1); // resize() 也可只写长度, 不赋初值
}
void add_edge(int u, int v, int w) {
pnt[e] = v, wv[e] = w;
nxt[e] = head[u], head[u] = e++;
}
void spfa_heap(int s) {
// 求最短路, 将 d[i] 赋初值为无穷大
for (int i = 1; i <= n; i++) d[i] = inf;
// 求最短路, 放到优先队列式加个负号
priority_queue<pair<T, int>> q;
q.push({-(d[s] = 0), s});
while (!q.empty()) {
auto [w, u] = q.top();
q.pop();
if (d[u] != -w) continue;
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = pnt[i];
T tmp = d[u] + wv[i];
if (tmp < d[v]) q.push({-(d[v] = tmp), v});
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, s, u, v, w;
cin >> n >> m >> s;
Graph<int> G(n, m * 2);
while (m--) {
cin >> u >> v >> w;
G.add_edge(u, v, w); // 有向图只添加 1 条边
// G.add_edge(v, u, w); // 无向图要添加 2 条边
}
G.spfa_heap(s);
for (int i = 1; i <= n; i++) cout << G.d[i] << " \n"[i == n];
return 0;
}
（点击展开）二维 vector 存储图+priority_queue 优化：写起来更简单，推荐
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
// template 是 C++ 的模板方法, 方便我们封装代码
template <typename T>
struct Graph {
int n; // n: 点的个数, m: 边的个数
vector<vector<pair<int, int>>> g; // 二维 vector 存储图
vector<T> d; // d[i] 表示起点到 i 的最短距离
Graph(int n_): n(n_) {
g.resize(n + 1);
d.resize(n + 1); // resize() 也可只写长度, 不赋初值
}
void add_edge(int u, int v, int w) {
g[u].push_back({v, w});
}
void spfa_heap(int s) {
// 求最短路, 将 d[i] 赋初值为无穷大
for (int i = 1; i <= n; i++) d[i] = inf;
// 求最短路, 放到优先队列式加个负号
priority_queue<pair<T, int>> q;
q.push({-(d[s] = 0), s});
while (!q.empty()) {
auto [w, u] = q.top();
q.pop();
if (d[u] != -w) continue;
for (auto [v, w] : g[u]) {
T tmp = d[u] + w;
if (tmp < d[v]) q.push({-(d[v] = tmp), v});
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, s, u, v, w;
cin >> n >> m >> s;
Graph<int> G(n);
while (m--) {
cin >> u >> v >> w;
G.add_edge(u, v, w); // 有向图只添加 1 条边
// G.add_edge(v, u, w); // 无向图要添加 2 条边
}
G.spfa_heap(s);
for (int i = 1; i <= n; i++) cout << G.d[i] << " \n"[i == n];
return 0;
}
输入格式
第一行为三个正整数 。 第二行起 行，每行三个非负整数 ，表示从 到 有一条权值为 的有向边。
输出格式
输出一行 个空格分隔的非负整数，表示 到每个点的距离。
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
0 2 4 3
提示
【样例 1 解释】
- 推荐一个在线画图工具, graph_editor
数据规模与限制
- ；
- ；
- ；
- ,
- 。