AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
Winkel
,
2020-11-04 19:29:44
,
所有人可见
,
阅读 380
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510;
int n,m;
int g[N][N], dis[N];
bool use[N];
int dijkstra()
{
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for(int i = 0; i < n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
{
if(!use[j] && (t == -1 || dis[t] > dis[j])) t = j;
}
use[t] = true;
for(int j = 1; j <= n; j++)
{
dis[j] = min(dis[j], dis[t] + g[t][j]);
}
}
if(dis[n] == 0x3f3f3f3f) return -1;
else return dis[n];
}
using namespace std;
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m--)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);
}
cout << dijkstra();
return 0;
}