畅通工程续

3 30 1 10 2 31 2 10 23 10 1 11 2 Sample Output
2-1 Authorlinle Source2008浙大研究生复试热身赛（2）——全真模拟 Recommendlcy   |   We have carefully selected several similar problems for you:  2544 2066 2112 1217 1875 
#include<cstdio>                //最短路不必须计算到每一个点 #include<algorithm>#define MAX 999999999using namespace std;int n,m,st,ed;               //n个城镇，m条路，起点，终点 int dp[211][211];             //表示两点间距离 int dis[211];                //某点到起点的距离 int vis[211];             //记录该点是否被计算过 int min(int a,int b){	return (a>b)?b:a;              //求较小者 }void init ()           //此函数赋初值 {	for(int i=0;i<n;i++)    {    	dis[i]=MAX;    	vis[i]=0;    	for(int j=0;j<n;j++)    	    dp[i][j]=dp[j][i]=MAX;	}}void dijkstra(){	dis[st]=0;	while(1)	{		int v=-1;		for(int i=0;i<n;i++)		{			if(!vis[i]&&(v==-1||dis[i]<dis[v]))			    v=i;		}		if(v==-1)//每一个点都计算过后，vis[i]都是1，不成立，则v==-1，结束循环 		    break;		vis[v]=1;   		for(int i=0;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))	{	    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]);//考虑路径重复，取最短的 	   }	    scanf("%d%d",&st,&ed);	    dijkstra();	    if(dis[ed]<MAX)	        printf("%d/n",dis[ed]);	    else	        printf("-1/n");	}	return 0;}