- 浏览: 35587 次
- 性别:
- 来自: 湖南
最新评论
-
kulinglei:
提烟而过 写道问下楼主:你是拿了别人的注册号在这里害别人,还是 ...
折半搜索 -
jy00105276:
没看代码,看描述难道是2分法?
是的话不一定是a[i-1] ...
折半搜索 -
提烟而过:
问下楼主:你是拿了别人的注册号在这里害别人,还是没事在这里装- ...
折半搜索 -
zqynux:
fffvvvzz 写道11-15
是
11 12 13 14 ...
折半搜索 -
zqynux:
额,, 就是一个NOIP题目的答案..
vijos 谁拿了最多奖学金
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.iteye.com/blog/626000
所以这方面我就不怎么说明了, 不过这个题目我从一开始就觉得奇怪, n的上限怎么是10000,, 不过没想太多, 就开始写了..., 写完提交试试,, 没AC,, 看了看数据, 和Z有关的只有一个Z a 100, 才想到这是一个无向带权的图, 稍加修改之后又被卡住了,, 到网上看了一下分析才想起来,, 题目里有这么一句话: "两个牧场(可能是字母相同的)之间会有超过一条道路相连。",, 而我们需要的只是最短的,, 所以我又修改了一下...
也就是说这个10000是有意义的~! 哈,, 还是怪自己审题不清楚..
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.iteye.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; }
发表评论
-
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 1263/* LANG: C ID: zqynux11 PROG ... -
重做 USACO 1.1 黑色星期五
2010-03-31 18:59 805解释什么的就算了吧,, /* LANG: C ID: ... -
重做 USACO 1.1 贪婪的送礼者
2010-03-31 18:58 1204这题的话, 我用的是个结构体, 记录各个人.. 我错了的地 ... -
重做 USACO 1.1 你的飞碟在这儿
2010-03-31 18:56 846不解释了.. /* LANG: C ID: zqynu ... -
USACO 3.1 Shaping Regions 形成的区域
2010-03-30 20:01 1493这题二话不说, 用map[i][j]表示坐标为i, j的点 ... -
USACO 3.1 Humble Numbers 丑数
2010-03-28 15:31 1439从这一题开始,, 以后题目我就不贴上来了... 自己去看吧 ... -
USACO 3.1 Score Inflation 总分
2010-03-27 20:19 799Score Inflation The more point ... -
USA 3.1 Agri-Net 最短网络
2010-03-27 20:14 839Agri-Net Russ Cox Farmer John ... -
USACO 2.4 Fractions to Decimals 分数化小数
2010-03-27 15:47 1243Fractions to Decimals Write a ... -
USACO 2.4 Cow Tours 牛的旅行
2010-03-27 11:57 1076Cow Tours Farmer John has a nu ... -
USACO 2.4 Overfencing 穿越栅栏
2010-03-25 18:18 930USACO 2.4 Overfencing 穿越栅栏 Over ... -
USACO 2.4 The Tamworth Two 两只塔姆沃斯牛
2010-03-23 22:05 1168The Tamworth Two BIO '98 - Rich ... -
USACO 2.3 Controlling Companies 控制公司
2010-03-23 22:00 1417Controlling Companies Some com ... -
USACO 1.1 Broken Necklace 破碎的项链
2010-03-22 18:04 2073Broken Necklace You have a neck ... -
USACO 2.3 Money Systems 货币系统
2010-03-22 13:31 948Money Systems The cows have no ... -
USACO 2.3 Cow Pedigrees 奶牛家谱
2010-03-21 15:02 1408Farmer John is considering purc ... -
USACO 2.3 Zero Sum 零的算式和
2010-03-20 14:30 1756Zero Sum Consider the sequence ... -
USACO Longest Prefix最长前缀
2010-03-17 12:28 1397Longest Prefix IOI'96 The stru ... -
vijos 谁拿了最多奖学金
2010-03-17 12:25 1063描述 Description 某校的惯例是在每 ... -
USACO 2.2 Subset Sums集合
2010-03-16 12:18 1421USACO 2.2 Subset Sums集合 For ...
相关推荐
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
usaco2.4解题报告1
USACO中的bessie come home,用C++编写,用了BFS的知识
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO题集及答案
USACO做题代码
USACO历年比赛测试数据:2003年 方便大家测试
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
USACO全部译题 USACO Training Program Gateway
内含USACO全部测试数据,绝对全
usaco traning的全部数据 才要3分
USACO所有题目的题解 NOCOW整理版
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO历年比赛测试数据:2006年方便大家测试
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了