AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
HUE菜鸡联盟
,
2021-12-06 19:39:57
,
所有人可见
,
阅读 112
//dijkstra算法可能无法准确算出存在负边的情况;复杂度:O(V^2);
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define for0(x,n) for(int x=0;x<n;x++)
#define for1(x,n) for(int x=1;x<=n;x++)
using namespace std;
const int tt=500+10,mod=1e6+7,INF=0x7f7f7f7f;
int n,m,ans,a[tt],t,b[tt];
char s[tt];
int cost[tt][tt];
int d[tt];
bool used[tt];
int V,E;
void dijkstra(int s)
{
fill(d,d+V+1,INF);
fill(used,used+V+1,false);
d[s]=0;
while(true)
{
int v=-1;
for(int u=1;u<=V;u++)
{
if(used[u]==0&&d[u]<d[v])v=u;
}//如果没有使用过,且当前点到原点的距离最小,那么就把u赋值给v,v为当前最小点;
if(v==-1)break;
used[v]=true;
for(int u=1;u<=V;u++)d[u]=min(d[u],d[v]+cost[v][u]);
// for1(i,V)cout<<d[i]<<' ';cout<<endl;
}
}
signed main()
{
memset(cost,0x7f7f7f7f,sizeof(cost));
cin>>V>>E;
while(E--)
{
int from,to,spend;
cin>>from>>to>>spend;
cost[from][to]=min(cost[from][to],spend);
}
dijkstra(1);
if(d[V]!=INF)cout<<d[V];
else cout<<-1;
}