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
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
解题心得：
- 因为数据量很小这就很简单了，用每个点跑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
",pos,Min);
}
return 0;
}