Aizu：0189-Convenient Location

Convenient Location

Time limit 1000 ms

Memory limit 131072 kB

Problem Description

明年毕业的A为就业而搬家。就职的公司在若干城市都有办公室，不同天出勤的办公室也不同。所以A在考虑住在哪去各个办公室的时长最短。

你为了帮助A，决定去找最方便的居住城市。

城市从0号开始编号，城市之间有道路。不同的道路对应着不同的通勤时间。A 从所住的城市到该城市的办公室的通勤时间认为是 0。此时考虑到所有城市的通勤时间。例如，城市和道路的设置如图所示，A 住在城市 1 的情形下，到不同城市的通勤时间是

到城市 0：80

到城市 1：0

到城市 2：20

到城市 3：70

到城市 4：90

，总和为 260。

输入道路的数量和所有道路的信息，求出到所有城市的通勤时间最小值和这个最小值对应的城市编号。若有多个城市的总通勤时间都是最小值，输出这些城市编号中的最小值。城市的总数不超过 10，道路的总数不超过 45，所有道路都是双向的，且两个方向的通勤时间是相等的。每个城市到其他任一城市都存在道路。

Input

有多组测试数据，输入由单行 0 终止。每个测试数据格式如下。

n

a1 b1 c1

a2 b2 c2

:

an bn cn

第1行给出道路数目 n (1 ≤ n ≤ 45) 。接下来 n 行给出第 i 个道路的信息。 ai, bi (0 ≤ ai, bi ≤ 9) 是第 i 个道路连接的城市的编号，ci (0 ≤ ci ≤ 100) 是这条道路的通勤时间。

Output

对每个测试数据，输出总通勤时间的最小值和对应最小的城市编号，由空格分开，结尾是换行符。

Sample Input

Output for the Sample Input

2 240

1 2

解题心得：

因为数据量很小这就很简单了，用每个点跑SPFA然后算出和，直接打印出最小的那个点就是了。

#include <stdio.h>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

const int maxn = 50;

int Time[maxn],Min,pos,n;

bool vis[maxn];

vector <pair<int,int> > ve[maxn];

void init() {

    pos = -1;

    Min = 0x7f7f7f7f;

    for(int i=0;i<=n;i++)

        ve[i].clear();

    int N = 0;

    for(int i=1;i<=n;i++) {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        ve[a].push_back(make_pair(b,c));

        ve[b].push_back(make_pair(a,c));

        N = max(N,a);

        N = max(N,b);

    }

    n = N;

}

void spfa(int s) {

    queue <int> qu;

    memset(vis,0,sizeof(vis));

    memset(Time,0x7f,sizeof(Time));

    qu.push(s);

    Time[s] = 0;

    while(!qu.empty()) {

        int now = qu.front(); qu.pop();

        vis[now] = false;

        for(int i=0;i<ve[now].size();i++) {

            int v = ve[now][i].first;

            int d = ve[now][i].second;

            if(d+Time[now] < Time[v]) {

                Time[v] = Time[now] + d;

                if(!vis[v]) {

                    qu.push(v);

                    vis[v] = true;

                }

            }

        }

    }

}

bool updata_Min() {

    int sum = 0;

    for(int i=0;i<=n;i++)

        sum += Time[i];

    if(sum < Min) {

        Min = sum;

        return true;

    }

    return false;

}

int main() {

    while(scanf("%d",&n) && n) {

        init();

        for(int i=0;i<=n;i++) {

            spfa(i);

            if(updata_Min()) {

                pos = i;

            }

        }

        printf("%d %d\n",pos,Min);

    }

    return 0;

}

巴特西