【题目来源】
AcWing：850. Dijkstra求最短路 II - AcWing题库
【题目描述】
给定一个\(n\)个点\(m\)条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出\(1\)号点到\(n\)号点的最短距离，如果无法从\(1\)号点走到\(n\)号点，则输出\(-1\)。
【输入】
第一行包含整数\(n\)和\(m\)。
接下来\(m\)行每行包含三个整数 \(x,y,z\)，表示存在一条从点\(x\)到点\(y\)的有向边，边长为\(z\)。
【输出】
输出一个整数，表示\(1\)号点到\(n\)号点的最短距离。
如果路径不存在，则输出\(-1\)。
【输入样例】
3 3
1 2 2
2 3 1
1 3 4
【输出样例】
3
【解题思路】
【算法标签】
《AcWing 850 Dijkstra求最短路II》 #最短路# #Dijkstra#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 150010; // 最大节点数
typedef pair<int, int> PII; // 用于优先队列的pair类型：(距离, 节点编号)int n; // 节点数量
int m; // 边数量
int h[N]; // 邻接表头数组
int w[N]; // 边权数组
int e[N]; // 边的终点数组
int ne[N]; // 下一条边数组
int idx; // 边的索引
int dist[N]; // 从起点到各点的最短距离
bool st[N]; // 标记节点是否已确定最短距离// 添加有向边 a->b，权重为c
void add(int a, int b, int c)
{e[idx] = b; // 存储边的终点w[idx] = c; // 存储边的权重ne[idx] = h[a]; // 新边指向原来的第一条边h[a] = idx; // 更新头指针指向新边idx++; // 边索引增加
}// 堆优化Dijkstra算法求单源最短路径
// 返回：起点1到终点n的最短距离，如果不可达返回-1
int dijkstra()
{// 第一步：初始化距离数组memset(dist, 0x3f, sizeof(dist)); // 所有距离初始化为无穷大dist[1] = 0; // 起点到自身的距离为0// 第二步：创建小顶堆优先队列// 优先队列按pair的第一个元素（距离）从小到大排序priority_queue<PII, vector<PII>, greater<PII>> heap;// 将起点加入优先队列heap.push({0, 1}); // (距离, 节点编号)// 第三步：处理优先队列直到为空while (heap.size()){// 取出堆顶元素（当前距离最小的节点）auto t = heap.top();heap.pop();int ver = t.second; // 节点编号int distance = t.first; // 当前距离// 如果这个节点已经确定最短距离，跳过（这是关键优化）if (st[ver]){continue;}// 标记节点ver已确定最短距离st[ver] = true;// 第四步：遍历节点ver的所有邻接边for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i]; // 邻接节点j// 如果通过ver到j的距离更短，则更新if (dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j}); // 将j和新距离加入优先队列}}}// 第五步：检查终点是否可达if (dist[n] == 0x3f3f3f3f){return -1; // 不可达}return dist[n]; // 返回最短距离
}int main()
{// 输入节点数和边数scanf("%d%d", &n, &m);// 初始化邻接表memset(h, -1, sizeof(h));// 输入m条有向边while (m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}// 执行Dijkstra算法int t = dijkstra();// 输出结果printf("%d\n", t);return 0;
}
【运行结果】
3 3
1 2 2
2 3 1
1 3 4
3