HDU 1874 暢通工程續 （Floyd）

某省自從實行了很多年的暢通工程計劃後，終于修建了很多路。不過路多了也不好，每次要從一個城鎮到另一個城鎮時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。

現在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。

Input

本題目包含多組資料，請處理到檔案結束。

每組資料第一行包含兩個正整數N和M(0<N<200,0<M<1000)，分别代表現有城鎮的數目和已修建的道路的數目。城鎮分别以0～N-1編号。

接下來是M行道路資訊。每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路。

再接下一行有兩個整數S,T(0<=S,T<N)，分别代表起點和終點。

Output

對于每組資料，請在一行裡輸出最短需要行走的距離。如果不存在從S到T的路線，就輸出-1.

Sample Input

3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
           

Sample Output

2
-1
           

注意：同一條道路之間的距離可能有多個，例如1和3之間的距離你在上邊輸的是一個2，而下邊還有一個1和3之間的距離是5。這樣5就把原來的2給覆寫了。這一點賊坑。

處理同一條路的多個距離，把這條路的最短距離存進去。

for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&v);
			if(e[a][b]>v)
			{
				e[a][b]=v;
				e[b][a]=v;
			}
		}
           

#include<stdio.h>

int main(void)
{
	int i,j,k;
	int m,n,a,b,v;
	int s,t;
	int e[210][210];
	int inf=99999999;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
					if(i==j)
					e[i][j]=0;
				else
					e[i][j]=inf;
			}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&v);
			if(e[a][b]>v)
			{
				e[a][b]=v;
				e[b][a]=v;
			}
		}
		for(k=0;k<n;k++)
			for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					if(e[i][j]>e[i][k]+e[k][j])
						e[i][j]=e[i][k]+e[k][j];
	
		scanf("%d%d",&s,&t);
		if(e[s][t]!=inf)
			printf("%d\n",e[s][t]);
		if(e[s][t]==inf)
			printf("-1\n");
	}
	return 0;
}