Aizu 0189 （最短路）

Description

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

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

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

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

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

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

Input

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

 1行目  道の数n(整数)
 2行目  第1の道の情報 a1 b1 c1(それぞれ整数;半角空白区切り)
              各記号の意味は以下のとおりです。
              a1 b1:この道がつないでいる町の番号
              c1:a1、b1間の通勤時間
 3行目 第2の道の情報 a2 b2 c2
     :
 n+1行目 第nの道の情報 an bn cn

Output

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

Sample Input

Output for the Sample Input

2 240
1 2


题意：（初看题目吓死宝宝了，日文诶，真得好好说说题意。）给你m条边，假若有n个点， 让你求 2 ，3 ... n 到1的距离和；1， 3,....n 到2的距离和，以此类推，问你在这些距离和当中， 最小的距离和是多少？

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define maxn 15
#define oo 0xfffffff
using namespace std;
int maps[maxn][maxn], dist[maxn], v[maxn], n;

void Init()
{
    for(int i=1; i<=12; i++)
    {
        for(int j=1; j<=12; j++)
        {
            if(i==j)
                maps[i][j] = 0;
            else
                maps[i][j]=maps[j][i]=oo;
        }

    }
}

int Dij(int s)
{
    memset(v, 0, sizeof(v));

    for(int i=1; i<=n; i++)
    dist[i] = maps[s][i];

    v[s] = 1;

    for(int i=1; i<n; i++)
    {
        int index=-1, mins=oo;
        for(int j=1; j<=n; j++)
        {
            if(!v[j]&&dist[j]<mins)
            {
                index = j;
                mins = dist[j];
            }
        }

        v[index] = 1;

        for(int j=1; j<=n; j++)
        {
            if(!v[j] && dist[j]>maps[index][j]+mins)
                dist[j] = maps[index][j]+mins;
        }
    }

    int ans = 0;

    for(int i=1; i<=n; i++)
        ans += dist[i];

 //printf("%d ", ans);
    return ans;
}


int main()
{
    int m;

    while(scanf("%d", &m), m)
    {
        Init();
        int a, b, c;
        n = 0;
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            a++;
            b++;
            maps[a][b]=maps[b][a]=min(maps[a][b], c);
            n = max(n, max(a, b));
        }

        int ans = oo;
        int index, sum;
        for(int i=1; i<=n; i++)
        {
            sum =Dij(i);
            if(ans>sum)
            {
                ans = sum;
                index = i;
            }
        }
        printf("%d %d
",index-1, ans);

    }
    return 0;
}

View Code