AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
梦都会空
,
2021-12-06 18:09:17
,
所有人可见
,
阅读 164
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dix[N];
bool st[N];
int fun() {
memset(dix, 0x3f, sizeof dix);
dix[1] = 0;
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j) {
if (!st[j] && (t == -1 || dix[j] < dix[t])) {
t = j;
}
}
st[t] = true;
for (int j = 1; j <= n; ++j) {
dix[j] = min(dix[j], dix[t] + g[t][j]);
}
}
if (dix[n] == 0x3f3f3f3f) return -1;// 如果起点到达不了n号节点,则返回-1
return dix[n];// 返回起点距离n号节点的最短距离
}
int main() {
cin >> 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);
}
cout << fun() << endl;
return 0;
}