- 浏览: 37637 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
USACO - 2.4.4 - Bessie Come Home
原创文章转载请注明出处
摘要:Dijkstra , 图论
一. 题目翻译
1. 描述:
现在是晚餐时间,而母牛们在外面分散的牧场中。 农民约翰按响了电铃,所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。 有时,两个牧场(可能是字母相同的)之间会有超过一条道路相连。 至少有一个牧场和谷仓之间有道路连接。 因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。 当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。 牧场被标记为'a'..'z'和'A'..'Y',在用大写字母表示的牧场中有一只母牛,小写字母中则没有。 谷仓的标记是'Z',注意没有母牛在谷仓中。
注意'm'和'M'不是同一个牧场, 否则错误。
2. 格式:
INPUT FORMAT:
第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。
第 2 ..P+1行: 用空格分开的两个字母和一个整数:
被道路连接牧场的标记和道路的长度(1<=长度<=1000)。
OUTPUT FORMAT:
单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。
SAMPLE INPUT:
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
SAMPLE OUTPUT:
B 11
二. 题解
1. 题意理解(将问题分析清楚,大致用什么思路):
图论的问题,计算出所有顶点到谷仓“Z”的距离,可以使用Dijkstra算法。
2. 启示:
Dijkstra算法,图论当中的基本算法,注意积累。
三. 代码
package session_2_4_4; /* ID:fightin1 LANG:JAVA TASK:comehome */ //package session_2_4_4; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; public class comehome { public static void main(String[] args) throws Exception { // BufferedReader in = new BufferedReader(new FileReader( // "comehome.in")); // PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter( // "comehome.out"))); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(System.out); int[][] roads = new int[52][52]; boolean[] visited = new boolean[52]; int[] distance = new int[52]; int roadsNum = Integer.parseInt(in.readLine()); for (int i=0;i<roadsNum;i++){ String[] temp = in.readLine().split(" "); char src = temp[0].charAt(0); char des = temp[1].charAt(0); int srcNum,desNum; int length = Integer.parseInt(temp[2]); if (src>='a'&&src<='z'){ srcNum = src-'a'; }else{ srcNum = src-'A'+26; } if (des>='a'&&des<='z'){ desNum = des-'a'; }else{ desNum = des -'A'+26; } if ((roads[srcNum][desNum]!=0&&length<roads[srcNum][desNum])||roads[srcNum][desNum]==0){ roads[srcNum][desNum] = length; roads[desNum][srcNum] = length; } } for (int i=51;i>=0;i--){ if (roads[51][i] == 0){ distance[i] = Integer.MAX_VALUE; } else { distance[i] = roads[51][i]; } } for (int i=0;i<51;i++){ int min = Integer.MAX_VALUE; int next = 51; for (int j=0;j<51;j++){ if (!visited[j]){ if (distance[j]<min){ next = j; min = distance[j]; } } } if (next == 51){ break; }else{ visited[next] = true; } for (int j=0;j<51;j++){ if (!visited[j]&&(roads[next][j]!=0)&&(min+roads[next][j]<distance[j])){ distance[j] = min + roads[next][j]; } } } int min = Integer.MAX_VALUE; int result = 51; for (int i=26;i<51;i++){ if (distance[i]<min){ result = i; min = distance[i]; } } pw.println((char)(result-26+'A')+" "+distance[result]); pw.close(); in.close(); } }
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 805原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 697原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1035原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 906原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 710原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 902原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 852原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 958原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 715原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1299原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 865原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 741原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1007原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1040原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1205原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 657原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 693原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 888原创文章转载请注明出处 摘要:模拟 , 数学分析 ... -
USACO - 2.1.5 - Hamming Codes
2012-08-18 19:22 779原创文章转载请注明出处 摘要:枚举、暴力 ...
相关推荐
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
USACO题目,Greedy Gift Givers
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
USACO-Cpp
Notes-USACO-2021-弹簧
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
我的USACO题解和程序
USACO中的bessie come home,用C++编写,用了BFS的知识
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide