最短路

2 11 2 33 31 2 52 3 53 1 20 0 Sample Output
32 SourceUESTC 6th Programming Contest Online Recommendlcy
#include<cstdio>#define MAX 999999999int dp[111][111];int dis[111]; int vis[111];int n,m,st,ed;int min(int a,int b){	return (a<b)?a:b;}void init(){	for(int i=1;i<=n;i++)	{		dis[i]=MAX;		vis[i]=0;		for(int j=1;j<=n;j++)		    dp[i][j]=dp[j][i]=MAX;	}}void dijkstra(){	dis[st]=0;//本题起点已知，所以也可直接写成dis[1]=0 	while(1)	{		int v=-1;//每次循环开始v值都是-1；所以要写在循环里面 		for(int i=1;i<=n;i++)		{			if(!vis[i]&&(v==-1||dis[i]<dis[v]))			    v=i;		}		if(v==-1)		   break;		vis[v]=1;		for(int i=1;i<=n;i++)		{			if(dis[i]>(dis[v]+dp[v][i]))			    dis[i]=dis[v]+dp[v][i];		}	}}int main(){	while(~scanf("%d%d",&n,&m)&&(n||m))	{		init();		while(m--)		{			int a,b,c;			scanf("%d%d%d",&a,&b,&c);			dp[a][b]=dp[b][a]=min(c,dp[a][b]);		}		st=1;		ed=n;		dijkstra();		printf("%d/n",dis[ed]);//终点也已知，也可直接写成dis[n],那么上面两个就不用写了 	}	return 0;}