AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
C___
,
2021-12-05 21:18:20
,
所有人可见
,
阅读 103
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
using LL = long long;
const int N = 1e5 + 10 + 5 * 1e4;
int n, m, d[510][510], dist[510];
bool st[510];
int Dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= n; i++){
int t = -1;
for(int j = 1; j <= n; j++){
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
st[t] = true;
for(int j = 1; j <= n; j++){
dist[j] = min(dist[j], dist[t] + d[t][j]);
}
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}
int main(void){
memset(d, 0x3f, sizeof d);
scanf("%d%d", &n, &m);
while(m--){
int a, b, c; scanf("%d%d%d", &a, &b, &c);
d[a][b] = min(d[a][b], c);
}
printf("%d\n", Dijkstra());
return 0;
}