AcWing 849. dijstra求最短路
原题链接
简单
作者:
尽量不说话
,
2021-02-19 23:57:46
,
所有人可见
,
阅读 349
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int g[N][N], dis[N];
int n , m, t;
bool st[N];
int dijstra()
{
memset(dis, 0x3f, sizeof dis);//最小距离初始化
dis[1] = 0;//1点初始化
for(int i = 0; i < n; i ++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
{
if(!st[j] && (t == -1 || dis[j] < dis[t]))
t = j;
}//寻找最小距离的待更新点
st[t] = true;
for(int j = 1; j <= n; j ++)
dis[j] = min(dis[j], g[t][j] + dis[t]);//以更新的点更新其他点
}
if(dis[n] == 0x3f3f3f3f)
return -1;
return dis[n];
}
int main()
{
memset(g, 0x3f, sizeof g);//初始距离赋为无穷
cin >> n >> m;
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);//可能存在重边
}
cout << dijstra() << endl;
}