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
题意:
给出 P(1 ~ 10000)条路,后给出这 P 条无向边的两端和距离(1 ~ 1000), 大写字母表示的是有牛的位置,小写字母表示该处没有牛但是有个转角点,终点是Z,求哪头牛最快到达终点,输出这头牛的编号和距离。
思路:
最短路 + Floyd。开 60 大小的数组,代表 A ~ Z 和 a ~ z 全部,同时用数组 cow 标记哪头牛是存在的,最后比较得出最小值即可。
AC:
/* TASK:comehome LANG:C++ ID:sum-g1 */ #include <stdio.h> #include <string.h> #include <algorithm> #define INF 99999999 using namespace std; int w[60][60]; bool cow[30]; void init() { for(int i = 0; i < 60; ++i) for(int j = 0; j < 60; ++j) w[i][j] = INF; for(int i = 0; i <= 26; ++i) cow[i] = false; } void floyd() { for(int k = 0; k < 60; ++k) for(int i = 0; i < 60; ++i) for(int j = 0; j < 60; ++j) if(w[i][k] < INF && w[k][j] < INF && w[i][j] > w[i][k] + w[k][j]) w[i][j] = w[i][k] + w[k][j]; } int main() { freopen("comehome.in","r",stdin); freopen("comehome.out","w",stdout); int n; init(); scanf("%d",&n); getchar(); while(n--) { char a,b; int dis; scanf("%c %c%d",&a,&b,&dis); getchar(); if(a >= 'A' && a <= 'Z') cow[a - 'A'] = true; if(b >= 'A' && b <= 'Z') cow[b - 'A'] = true; w[a - 'A'][b - 'A'] = min(w[a - 'A'][b - 'A'],dis); w[b - 'A'][a - 'A'] = min(w[b - 'A'][a - 'A'],dis); } floyd(); int min_step = INF; char min_cow; for(int i = 0; i < 25; ++i) if(cow[i] && w[i][25] < min_step) { min_step = w[i][25]; min_cow = 'A' + i; } printf("%c %d\n",min_cow,min_step); return 0; }
相关推荐
USACO中的bessie come home,用C++编写,用了BFS的知识
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
深入讲解冒泡排序的实现及思想,对于初学者理解冒泡排序有一定的帮助
GEOS是一个C ++ 11库,用于在二维矢量几何上执行操作。 它主要是JTS拓扑套件Java库的端口。...生成状态分支/ CI Debbie Winnie Dronie Travis CI GitLab CI AppVeyor Bessie Bessie32 master 3.8 3.7
USACO-Cpp
平台游戏JS Capstone 钻石收藏家 目录 现场演示 关于该项目 一个名为Diamond Collector的平台游戏,该游戏的想法取材于著名的Endless Runner游戏,但具有升级的UI,UX和动画。 建于 JavaScript ...
The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that ...
One day, Bessie was gazing off into the distance at the beautiful Wisconsin mountains when she wondered to herself: which mountain is the widest one? She decided to take N (1 ,000) equally-spaced ...
Cow c1 = Cow(name("Bessie")); // Construct a second cow with a different name, and an optional age. // Also, specifying a type is optional, since InFact does type inference....
Bessie: Bessie32: Berrie: Berrie64: This file is here to play nicely with modern code repository facilities. Actual readme is . Official code repository, issue tracker and wiki: Official chat room: ...
SQL语法大全 SQL语法大全 1. ASP与Access数据库连接: dim conn,mdbfile mdbfile=server.mappath("数据库名称.mdb") set conn=server.createobject("adodb.connection") conn.open "driver={microsoft access ...
成星成一个简单的基于计时器的游戏。 在仍有时间的情况下,帮助Bessie唱尽可能多的音符! 播放。口香糖机David Su的所有资产,Louis Fineberg的Life Is Goofy字体除外。
关于eTOM的中文详细介绍!
Bessie 必须通过的所有步骤,并找到最大的距离增量。 我能够这么快地弄清楚这一点,因为我之前的 LeetCode 挑战之一遵循了类似的想法(计算总成本,计算出每一步的减少量,并返回减少量最大的步骤)。 曼哈顿距离的...
(1)使用SQL Server管理平台创建“学生管理”数据库。 要求:它有3个数据文件,其中主数据文件为20MB,最大为100MB,每次增加5MB;次数据文件为10MB,最大容量不受限制,每次增长20%﹔事务日志文件为20MB,最大为100MB,每次...
天地图最新版androidSDKDemo_V3.0.1 代码范例,包括地图显示,定位,POI搜索,路线规划等
自定义view控件,并定义了控件属性,适合新手学习
遥感图像处理课程设计 厦门市四期影像动态监测 遥感图像处理课程设计
离散数学看完学习视频以后即可食用本文档的题目,题目来源于平时上课的例题
实验目的与要求 (1)了解SQL Server 2019安装的硬件要求和软件环境。 (2)掌握SQL Server 2019 各组件的主要功能。 (3)了解数据库及其数据库对象。 (4)掌握SQL Server管理平台与查询编辑器的使用。...