给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
数据范围
1≤n≤5001≤n≤500,1≤m≤1051≤m≤105,图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=
510;
int dis[N],g[N][N],m,n;
bool st[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(!st[j]&&(t==-
1||dis[t]>
dis[j]))
t=
j;
}
st[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;
return dis[n];
}
int main(
void){
cin>>n>>
m;
memset(g,0x3f,
sizeof(g));
while(m--
){
int a,b,c;
cin>>a>>b>>
c;
g[a][b]=
min(g[a][b],c);
}
cout<<dijkstra()<<
endl;
return 0;
}
转载于:https://www.cnblogs.com/programyang/p/11184835.html
相关资源：dijkstra求最短路问题算法
