Convenient Location (最短路)

便利な町

来春卒業するAさんは、就職を機に引越しをすることにしました。就職する会社は、オフィスがいくつかの町にあって、日によって出勤するオフィスが違います。そこでAさんは,どこのオフィスに 行くにも時間の短い町に住もうと考えました。

そこであなたは、Aさんを助けるため、住むのに一番便利な町を探すことになりました。

町には 0 から始まる番号が振られており、町と町の間には道があります。それぞれの道に対して通勤時間が決まっています。Aさんがある町に住んでいる場合に、自分の町のオフィスまでの通勤時間は 0 とします。このときに全ての町までの通勤時間の総和を考えます。例えば、町と道の配置が上の図のようになっていて、Aさんが町1に住んだ場合には、それぞれの町までの通勤時間は 

町 0 まで 80
町 1 まで 0
町 2 まで 20
町 3 まで 70
町 4 まで 90

となり、総和は 260 となります。

道の数と、全ての道の情報を入力とし、それぞれの町に住んだ場合の通勤時間の総和を計算し、それが最小となる町の番号と、そのときの通勤時間の総和を出力するプログラムを作成してください。ただし、通勤時間の総和が最小となる町が複数ある場合は、一番小さい町の番号及びその時の通勤時間の総和を出力してください。町の総数は 10 以下、道の総数は 45 以下とし、全ての道は双方向に移動でき、通勤時間は方向によって変わらないものとします。また、どの町からでもその他全ての町への 経路があるものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下の形式で与えられます。

n
a1 b1 c1
a2 b2 c2
:
an bn cn

１行目に道の数 n (1 ≤ n ≤ 45) が与えられます。続く n 行に i 番目の道の情報が与えられます。 ai, bi (0 ≤ ai, bi ≤ 9) は i 番目の道がつないでいる町の番号、ci (0 ≤ ci≤ 100) はその道の通勤時間を表します。

Output

データセット毎に、通勤時間の総和が最小になる町の番号及びその時の通勤時間の総和を空白区切りで１行に出力します。

Sample Input

6     
0 1 80
1 2 20
0 2 60
2 3 50
3 4 60
1 4 90
2
0 1 1
1 2 1
0

Output for the Sample Input

2 240
1 2

思路

这道题用到了最短路的思想。先用一个二维数组来记录两个镇之间的距离，然后分别计算从 i 镇到 j 镇的最短距离，最后才计算所有路的最短距离。

#include <iostream>
#include <stdio.h>using namespace std;
int x,y,z,n,m;
const int inf=99999999;
int a[12][12],dis[12][12];int floyd(int x)
{int i,j,k;for(k=0;k<=x;k++){for(i=0;i<=x;i++){for(int j=0;j<=x;j++){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//搜寻更短路径}}}
}int main()
{while(scanf("%d",&n)!=EOF){if(n==0)break;for(int i=0;i<12;i++)//重置数组{for(int j=0;j<12;j++){if(i==j)dis[i][j]=0;elsedis[i][j]=inf;}}m=0;for(int i=0;i<n;i++){scanf("%d %d %d",&x,&y,&z);dis[x][y]=dis[y][x]=z;m=max(max(x,y),m);//寻找序号最大的城镇}floyd(m);int minn=inf,ans,num=0;for(int i=0;i<=m;i++){ans=0;for(int j=0;j<=m;j++){ans+=dis[i][j];//记录从i镇到其他所有镇的最短距离}if(ans<minn){minn=ans;num=i;}}printf("%d %d\n",num,minn);}return 0;
}