AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-18 10:33:26
,
所有人可见
,
阅读 251
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int diskstra() {
//首先将二维数组中的每一个位置都初始化为正无穷
memset(dist, 0x3f, sizeof dist);
//此时表示1号节点距离源点的距离为0
dist[1] = 0;
//对于其中每一个顶点来进行操作
for (int i = 0; i < n; i ++) {
//此时第一步是找到没有确定最短路的点中, 距离最小的
int t = -1; // 此时t == -1; 用来记录此轮中是那个点被确定。
for (int j = 1; j <= n; j ++) {
//如果此时j点还没有确定最短路,并且源点到t的距离 > 源点到j的距离
//在第一步的时候, (t == -1 || dist[t] > dist[j])是一定成立的
//此时t == -1简直了, 就是来处理开始节点的!!!!
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
st[t] = true; //此时将t加入到集合当中去
//此时来使用t这个点来更新其他点的距离
for (int j = 1; j <= n; j ++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m --) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
//此时表示如果有多重边的情况,取得最小值的情况。
g[a][b] = min(g[a][b], c);
}
printf("%d", diskstra());
return 0;
}