【题目来源】
AcWing：849. Dijkstra求最短路 I - 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 849 Dijkstra求最短路I》 #最短路# #Dijkstra#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 510; // 最大节点数
const int INF = 0x3f3f3f3f; // 无穷大int n; // 节点数量
int m; // 边数量
int g[N][N]; // 邻接矩阵存储图
int dist[N]; // 从起点到各点的最短距离
bool st[N]; // 标记节点是否已确定最短距离// Dijkstra算法求单源最短路径
// 返回：起点1到终点n的最短距离，如果不可达返回-1
int dijkstra()
{// 第一步：初始化距离数组memset(dist, 0x3f, sizeof(dist)); // 所有距离初始化为无穷大dist[1] = 0; // 起点到自身的距离为0// 第二步：循环n次，每次确定一个最短距离节点for (int i = 0; i < n; i++){// 找到未确定最短距离节点中，距离起点最近的节点tint t = -1; // 存储当前最小距离节点的编号for (int j = 1; j <= n; j++){// 如果节点j未确定最短距离，且// 1) 这是第一个满足条件的节点 (t==-1)// 2) 或者节点j的距离比当前最小值更小if (!st[j] && (t == -1 || dist[t] > dist[j])){t = j; // 更新当前最小值节点}}// 标记节点t已确定最短距离st[t] = true;// 第三步：用节点t更新其他未确定节点的距离for (int j = 1; j <= n; j++){// 如果从起点经过t到j的距离比当前记录更短，则更新dist[j] = min(dist[j], dist[t] + g[t][j]);}}// 第四步：检查终点是否可达if (dist[n] == INF){return -1; // 不可达}return dist[n]; // 返回最短距离
}int main()
{// 输入节点数和边数scanf("%d%d", &n, &m);// 初始化邻接矩阵memset(g, 0x3f, sizeof(g));// 输入m条边while (m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);// 处理重边：如果有重边，只保留权重最小的一条g[a][b] = min(g[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