暢通工程續 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

不明白Floyd算法的先看Floyd算法詳解

#include<iostream>
#include<algorithm>
using namespace std;
int inf=9999999; 
int main()
{
	int map[210][210],n,m,a,b,c;
    while(cin>>n>>m)
    {
    	for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
	        if(i==j)
		    map[i][i]=0;
		    else
			map[i][j]=inf;
		}
		for(int i=0;i<m;i++)
        {   
            cin>>a>>b>>c;
			if(c<map[a][b])
			map[a][b]=map[b][a]=c;
        }  
        for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(map[i][k]+map[k][j]<map[i][j])
        map[i][j]=map[i][k]+map[k][j];
        int x,y;
        cin>>x>>y;
        if(map[x][y]==inf)
        printf("-1\n");
        else printf("%d\n",map[x][y]);
    }
    return 0;
}