【题目来源】
洛谷：P4779 【模板】单源最短路径（标准版） - 洛谷
【题目描述】
给定一个 \(n\) 个点，\(m\) 条有向边的带非负权图，请你计算从 \(s\) 出发，到每个点的距离。
数据保证你能从 \(s\) 出发到任意点。
【输入】
第一行为三个正整数 \(n,m,s\)。 第二行起 \(m\) 行，每行三个非负整数 \(u_i,v_i,w_i\)，表示从 \(u_i\) 到 \(v_i\) 有一条权值为 \(w_i\) 的有向边。
【输出】
输出一行 \(n\) 个空格分隔的非负整数，表示 \(s\) 到每个点的距离。
【输入样例】
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
【算法标签】
《洛谷 P4779 单源最短路径（标准版）》 #图论# #优先队列# #最短路# #模板题#
【代码详解】
//堆优化Dijkstra
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;const int N = 100010; // 最大顶点数
int n, m, s; // n: 顶点数, m: 边数, s: 起点
int a, b, c; // 临时变量: 起点, 终点, 权重struct edge
{int v; // 邻接顶点int w; // 边权重
};
vector<edge> e[N]; // 邻接表存储图
int d[N]; // 最短距离数组
int vis[N]; // 标记顶点是否已出队/*** Dijkstra算法实现（堆优化）* 求从起点s到所有其他顶点的最短路径* 注意：这里使用大根堆，通过存入负距离实现小根堆功能* @param s 起始顶点*/
void dijkstra(int s)
{// 初始化距离数组memset(d, 0x3f, sizeof d); // 初始化为无穷大d[s] = 0; // 起点到自身距离为0// 使用大根堆存储(-距离, 顶点)对// 通过存储负距离，模拟小根堆的效果priority_queue<pair<int, int>> q; // 默认是大根堆// 起点入队q.push({0, s}); // 距离为0，顶点为s// 主循环while (q.size()){// 取出堆顶元素auto t = q.top();q.pop();int u = t.second; // 获取顶点编号// 如果顶点已出队，跳过if (vis[u]){continue; // 再出队跳过}vis[u] = 1; // 标记u已出队// 遍历u的所有邻接边for (auto ed : e[u]){int v = ed.v; // 邻接顶点int w = ed.w; // 边权重// 松弛操作if (d[v] > d[u] + w){d[v] = d[u] + w; // 更新最短距离// 入队，存储负距离以实现小根堆q.push({-d[v], v}); // 大根堆，负数使距离小的在堆顶}}}
}int main()
{// 输入顶点数、边数、起点cin >> n >> m >> s;// 构建邻接表for (int i = 0; i < m; i++){cin >> a >> b >> c;e[a].push_back({b, c}); // 添加有向边}// 执行Dijkstra算法dijkstra(s);// 输出结果for (int i = 1; i <= n; i++){printf("%d ", d[i]);}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 最大顶点数
const int M = 200005; // 最大边数int n, m, s; // n: 顶点数, m: 边数, s: 起点
int h[N]; // 邻接表头指针
int e[M], ne[M], w[M]; // 链式前向星: 终点, 下一条边, 权重
int idx; // 边的索引
int dist[N]; // 起点到各点的最短距离
bool st[N]; // 标记顶点是否已确定最短路径typedef pair<int, int> PII; // 存储(距离, 顶点)
priority_queue<PII, vector<PII>, greater<PII> > heap; // 小根堆/*** 添加有向边* @param a 起点* @param b 终点* @param c 权重*/
void add(int a, int b, int c)
{e[idx] = b; // 边指向的顶点w[idx] = c; // 边的权重ne[idx] = h[a]; // 指向原链表头h[a] = idx++; // 更新头指针
}/*** 堆优化的Dijkstra算法* 计算从起点s到所有顶点的最短路径* 注意：第22行代码有错误，应为dist[s] = 0* @param s 起始顶点*/
void dijkstra(int s)
{// 初始化所有距离为无穷大memset(dist, 0x3f, sizeof(dist));// 错误：这里应该设置dist[s] = 0，而不是dist[1] = 0dist[1] = 0; // 错误！应该是dist[s] = 0// 起点入堆heap.push({0, s});while (!heap.empty()){// 取出堆顶(距离最小的顶点)auto t = heap.top();heap.pop();int veid = t.second; // 顶点编号int distance = t.first; // 当前距离// 如果顶点已确定最短路径，跳过if (st[veid] == true){continue;}st[veid] = true; // 标记为已确定// 遍历veid的所有邻接边for (int i = h[veid]; i != -1; i = ne[i]){int j = e[i]; // 邻接顶点// 松弛操作：如果通过veid到j的路径更短if (dist[j] > distance + w[i]){dist[j] = distance + w[i]; // 更新最短距离heap.push({dist[j], j}); // 新距离入堆}}}
}int main()
{// 输入顶点数、边数、起点cin >> n >> m >> s;// 初始化邻接表memset(h, -1, sizeof(h));// 读入边for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;add(a, b, c); // 添加有向边}// 执行Dijkstra算法dijkstra(s);// 输出结果for (int i = 1; i <= n; i++){cout << dist[i] << " ";}cout << endl;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