7-19 单源点最短路(Dijkstra) (10 分)
Y老师被邀请参加一个会议，是在城市n(n<=2000)，而Y老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。
现在给出直接相邻城市的路长度，Y老师想知道从城市1到城市n，最短多少距离。
输入格式:
输入n, m，表示n个城市和m(m<=100000)条路;
接下来m行，每行a b c， 表示城市a与城市b有长度为c(c<=1000)的路。
输出格式:
输出1到n的最短路。如果1到达不了n，就输出-1。
输入样例:
5 5 1 2 20 2 3 30 3 4 10 4 5 20 1 5 100
输出样例:
80
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
10000 ms
内存限制
#include<bits/stdc++.h>
using namespace std;
int w[2000][2000];
int dis[2000],vis[2000];
const int inf=0x3f3f3f3f;
int main(){
int m,n;
scanf("%d%d",&n,&m);
int z,y,x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
w[i][j]=inf;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
w[x][y]=min(w[x][y],z);
w[y][x]=w[x][y];
}
for(int i=1;i<=n;i++)
dis[i]=w[1][i];
dis[1]=0;
vis[1]=1;
for(int i=1;i<=n;i++){
int k=0;
int minn=inf;
for(int j=1;j<=n;j++){
if(vis[j]==0&&dis[j]<minn){
minn=dis[j];
k=j;
}
}
if(k==0)
break;
vis[k]=1;
for(int j=1;j<=n;j++)
if(dis[j]>dis[k]+w[k][j])
dis[j]=dis[k]+w[k][j];
}
if(dis[n]!=inf)
printf("%d",dis[n]);
else
printf("-1");
return 0;
}