Bessie Come Home
Kolstad & Burch
It’s dinner time, and the cows are out in their separate pastures. Farmer John rings the bell so they will start walking to the barn. Your job is to figure out which one cow gets to the barn first (the supplied test data will always have exactly one fastest cow).
Between milkings, each cow is located in her own pasture, though some pastures have no cows in them. Each pasture is connected by a path to one or more other pastures (potentially including itself). Sometimes, two (potentially self-same) pastures are connected by more than one path. One or more of the pastures has a path to the barn. Thus, all cows have a path to the barn and they always know the shortest path. Of course, cows can go either direction on a path and they all walk at the same speed.
The pastures are labeled ‘a’..’z’ and ‘A’..’Y’. One cow is in each pasture labeled with a capital letter. No cow is in a pasture labeled with a lower case letter. The barn’s label is `Z’; no cows are in the barn, though.
PROGRAM NAME: comehome
INPUT FORMAT
Line 1: Integer P (1 <= P <= 10000) the number of paths that interconnect the pastures (and the barn)
Line 2..P+1: Space separated, two letters and an integer: the names of the interconnected pastures/barn and the distance between them (1 <= distance <= 1000)
SAMPLE INPUT (file comehome.in)
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
OUTPUT FORMAT
A single line containing two items: the capital letter name of the pasture of the cow that arrives first back at the barn, the length of the path followed by that cow.
SAMPLE OUTPUT (file comehome.out)
B 11
描述
现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时，两个牧场(可能是字母相同的)之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。牧场被标记为’a’..’z’和’A’..’Y’,在用大写字母表示的牧场中有一只母牛,小写字母中则没有。谷仓的标记是’Z’,注意没有母牛在谷仓中。
注意’m’和’M’不是一个牧场 否则错误
格式
PROGRAM NAME: comehome
INPUT FORMAT
第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。
第 2 ..P+1行: 用空格分开的两个字母和一个整数:
被道路连接牧场的标记和道路的长度(1<=长度<=1000)。
SAMPLE INPUT
(file comehome.in)
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
OUTPUT FORMAT
单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。
SAMPLE OUTPUT
(file comehome.out)
B 11
========================= 华丽的分割线 =========================
这题是自己独立完成的,, 喜一个(以前的话都是看着提示和标程之后完成的..)
思路的话和上一题的思路差不多,, http://zqynux.javaeye.com/blog/626000
所以这方面我就不怎么说明了, 不过这个题目我从一开始就觉得奇怪, n的上限怎么是10000,, 不过没想太多, 就开始写了…, 写完提交试试,, 没AC,, 看了看数据, 和Z有关的只有一个Z a 100, 才想到这是一个无向带权的图, 稍加修改之后又被卡住了,, 到网上看了一下分析才想起来,, 题目里有这么一句话: "两个牧场(可能是字母相同的)之间会有超过一条道路相连。",, 而我们需要的只是最短的,, 所以我又修改了一下…
也就是说这个10000是有意义的~! 哈,, 还是怪自己审题不清楚..
/*
LANG: C
ID: zqy11001
PROG: comehome
*/
#include <stdio.h>
#define getint(i) scanf(%d\\n, &i)
#define getmark(a, i) if(i >= \'A\' && i <= \'Z\'){\\
a = 26 + i - \'A\';\\
}else{\\
a = i - \'a\';\\
}
#define MAX 52
#define INF (1e9)
int map[MAX][MAX];
int n;
void mark(char i, char j, int t)
{
int a, b;
getmark(a, i);
getmark(b, j);
if(map[a][b] != 0){
if(t < map[a][b]){
map[a][b] = t;
map[b][a] = t;
}
return ;
}
map[a][b] = t;
map[b][a] = t;
}
int main(void)
{
int i, j, k, t;
int min = INF, m;
char a, b;
freopen(comehome.in, r, stdin);
freopen(comehome.out, w, stdout);
getint(n);
for(i = 0; i < n; i++){
scanf(%c %c %d\\n, &a, &b, &t);
mark(a, b, t);
}
for(i = 0; i < MAX; i++){
for(j = 0; j < MAX; j++){
if(map[i][j] == 0 && i != j){
map[i][j] = INF;
}
}
}
for(k = 0; k < MAX; k++)
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++){
if(map[i][j] > map[i][k] + map[k][j]){
map[i][j] = map[i][k] + map[k][j];
map[j][i] = map[i][k] + map[k][j];
}
}
for(i = 26; i < MAX - 1; i++){
if(map[i][51] < min && map[i][51] != 0){
min = map[i][51];
m = i;
}
}
printf(%c %d\\n, m - 26 + \'A\', min);
return 0;
}