Til the Cows Come Home

Description

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.
Input

  • Line 1: Two integers: T and N

  • Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.
    Output

  • Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.
    Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output

90
Hint

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

0

1个回答

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
Til the Cows Come Home(最短路,注意重边)
题目链接:http://poj.org/problem?id=2387   Description Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking....
poj 2387 Til the Cows Come Home spfa基础题,入门,我的第一个
终于想到spfa的好处了,首先要比dij快啊!!dij是所有点汤一遍,而spfa用链表有方向的,还有dij遇见负权边就完了dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2. 按dij算法求求看。  实现方法:建立一个队列,初始时队列里只有起始点,在建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋
【最短路】Til The Cows Come home(裸题)
参考:https://blog.csdn.net/major_zhang/article/details/72519233自己写的简单Dijkstra:#include &amp;lt;stdio.h&amp;gt; #include &amp;lt;algorithm&amp;gt; #include &amp;lt;vector&amp;gt; #include &amp;lt;iostream&amp;gt; #include &amp;lt;string.h&amp;...
(Til the Cows Come Home )链式前向星存图,优先队列,dijkstra算法
题目链接  USACO 2004 November 下面只是介绍模板,对于这道题还要注意边和顶点的输入顺序,下面的模板都是按照先顶点后边的顺序处理的,直接复制 提交会wa的,所以最好是自己理解着做,要是偷懒直接复制wa了别怪我 常规易于理解的方法 #include &amp;lt;stdio.h&amp;gt; #include &amp;lt;queue&amp;gt; #include &amp;lt;string.h&amp;...
Til the Cows Come Home(最短路算法母题)
原题链接 Til the Cows Come Home Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 45313 Accepted: 15372 DescriptionBessie is out in the field and wants to get back to the barn to g
POJ 2387 Til the Cows Come Home(迪杰斯特拉/优先队列/最短路)
题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18265 代码: #include #include #include using namespace std; const int maxn=2005; vector >E[maxn]; int d[maxn]; int n,m; void init() {
USACO历年比赛测试数据:2004年
USACO历年比赛测试数据:2004年,方便大家测试
Til the Cows Come Home
DescriptionnnBessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible. nnFarmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it. nnGiven the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.nInputnn* Line 1: Two integers: T and N nn* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.nOutputnn* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.nSample Inputnn5 5n1 2 20n2 3 30n3 4 20n4 5 20n1 5 100nSample Outputnn90nHintnnINPUT DETAILS: nnThere are five landmarks. nnOUTPUT DETAILS: nnBessie can get home by following trails 4, 3, 2, and 1.
最短路径 dj 迪杰斯特拉dijkstra
DJ 直接看题: Til the Cows Come Home Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her ...
Til the Cows Come Home (有向图最短路径问题)
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M≤ 100,000) unidirectional (one-way roa...
畅通工程续 + Til the Cows Come Home(最短路)
【板子】 板子要理解,要熟练。 https://blog.csdn.net/qq_41117236/article/details/80517605 【一】 畅通工程续 TimeLimit:1000MS  MemoryLimit:32768KB 64-bit integer IO format:%I64d Problem Description 某省自从实行了很多年的畅通工程计划后...
Til the Cows Come Home(最短路(单源SPFA))
Link:http://poj.org/problem?id=2387 Til the Cows Come Home Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 31889   Accepted: 10809 Description
Til the Cows Come Home(单源最短路)(Dijstra模板题)
Til the Cows Come Home Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep...
Til the Cows Come Home (最短路问题, 模板)
题目:https://vjudge.net/problem/POJ-2387  Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie nee...
Til the Cows Come Home (求图中的最短路)
Til the Cows Come Home Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty slee...
poj 2140 Herd Sums 判断S由连续的自然数组成共有几种情况
<br />Herd SumsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 11551 Accepted: 6891<br />DescriptionThe cows in farmer John's herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the ba
poj 2387 Til the Cows Come Home 最短路(贝尔曼,迪杰斯特拉,spfa)
Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get b
最短路模板问题:Til the Cows Come Home【最短路】
Til the Cows Come Home  POJ - 2387  Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs h...
Til the Cows Come Home (最短路矩阵存图去重边)
Til the Cows Come Home  POJ - 2387    #include&amp;lt;iostream&amp;gt; #include&amp;lt;cstring&amp;gt; using namespace std; const int maxn=2005; #define inf 0x3f3f3f3f int a[maxn][maxn]; int m,n; int dis[maxn]; i...
poj——2387——Til the Cows Come Home(简单最短路)
Description Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she
算法分析与复杂性理论 第三题 Til the Cows Come Home
总时间限制: 1000ms 内存限制: 65536kB 描述Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her
最短路和差分约束(三种算法实现)( Til the Cows Come Home )
题目训练链接(密码hpuacm): https://vjudge.net/contest/246705 我会分别用 迪杰斯特拉  优先队列和链式前向星优化过的迪杰斯特拉  SPFA算法 三种方法讲一下例题。 此外上述三种算法是求单源最短路问题, 这里还会介绍一下多源最短路的算法 floyd算法。多源最短路可以求出任意两点间的最短距离。 在存图方式中会用到邻接矩阵 链式前向星等存图方式,不知道...
USACO2.4.4 Bessie Come Home 回家 解题报告(模拟)
Description 现在是晚餐时间,而母牛们在外面分散的牧场中。 农民约翰按响了电铃,所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。 有时,两个牧场(可能是自我相同的)之间会有超过一...
Bessie Come Home 回家(最短路)
Description 现在是晚餐时间,而母牛们在外面分散的牧场中。 农民约翰按响了电铃,所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只速度最快的母牛)。 在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。 每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。 有时,两个牧场(可能是自我相同的)之间会有超过一...
百练 / 2017研究生推免上机考试 H: Til the Cows Come Home
题目来源:http://poj.org/problem?id=2387----------------------------------------Til the Cows Come Home总时间限制: 1000ms     内存限制: 65536kB描述Bessie is out in the field and wants to get back to thebarn to get as ...
POJ 2387 Til the Cows Come Home(图论几个基本算法的初探)
Til the Cows Come HomeTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 65500 Accepted: 22064DescriptionBessie is out in the field and wants to get back to the barn to get as much sleep as pos...
POJ 2387 Til the Cows Come Home (最短路径 模版题 三种解法)
原题链接:Til the Cows Come Home 题目大意:有  个点,给出从  点到  点的距离并且  和  是互相可以抵达的,问从  到  的最短距离。   题目分析:这是一道典型的最短路径模版题,需要注意的是:使用dijkstra算法求解需要考虑有重复边问题,而使用bellman-ford算法 和 spfa算法 可以忽略这个问题。 代码如下: // Dijkstra #in...
【最短路各种方法求解一题(模板题)】POJ 2387 Til the Cows Come Home
Problem Description 输入T,N分别代表有T条通道,和N个地点。接下来T行u,v,w分别表示u地点于v地点之间通道消费,有重复边 Sample Input 5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100 Sample Output 90 代码:dijkstra,就不带注
2140 Herd Sums
The cows in farmer John's herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N. Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7+8, 4+5+6, and 1+2+3+4+5. When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10. Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem.
TIL传输中过期
最开始是连不上测试的数据库,然后用在cmd界面ping数据库的地址ping不通,出现这个报错,一开始按照网上思路,使用ipconfig/flushcdn清除缓存,但是没有用效果。 后来发现其实是自己的电脑跟开发库不是在一个网段里面,于是在tcp4里面再设置一个跟开发库同一个网段的ip即可 ...
Bulls and Cows问题及解法
299. Bulls and Cows LeetCode
.zshrc配置最佳实战
# If you come from bash you might have to change your $PATH. # export PATH=$HOME/bin:/usr/local/bin:$PATH # Path to your oh-my-zsh installation. export ZSH=$HOME/.oh-my-zsh # Set name of the theme ...
【POJ】 2182 - Lost Cows 【线段树入门】
题目: Lost Cows Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9727   Accepted: 6261 Description N (2 <= N <= 8,000) cows have unique brands in the range
英语歌曲:Home(家)
Another summer day 又一个夏天 Has come and gone away 来了又走 In Paris or Rome… 在巴黎或者罗马 But I wanna go home 但是我只想回家… uhmMay be surrounded by 可能被成千上万的人 A million people I 所拥戴追逐 但我 Still feel al
poj3617字典序问题【贪心】
!!!好大一个坑…字符输入是一个一个的!!! 可以用cin.getline();但是时间慢,           也可以用 scanf("%s", tmp);s[i] = tmp[0]; 参考了网上的思路发现,还可以用scanf(" %c", &ch); 在格式串中,空格的意思是匹配输入中的所有换行、TAB、空格,所以加上一个空格,就可以屏蔽掉在输入中的所有的不愉快的因素了。 我的
HDOJ 题目2709Sumsets(递推)
Sumsets Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1460    Accepted Submission(s): 574 Problem Description Farmer John commanded h
come true和realize有什么区别?
come true和realize都有“实现”的意思,那么它们有什么区别? 我在做作业过程中遇到一道改错题。如下: If I work hard,I am sure I can come true my dre-ams one day. 答案说要把COME TRUE 改成REALIZE, come true和realize都有“实现”的意思,那么它们有什么区别? 应该改为:
POJ---2456(Aggressive cows,贪心最大化最小值)
题意: 有N头牛,其中有M头倔牛,要求最大化这M头牛最小距离。   题解: 最大化最小值,二分!对于所有的距离贪心判断这M头牛是否能放下去。   个人认为本题数据有问题,对于M=2的时候,好像~~~没有判定! 因为代码中初始化ub为x[N-1]-x[0]或者x[N-1]-x[0]+1都能AC。显然前者是错误的!  #include #include #include #includ
POJ2456(Aggressive cows)(贪心+二分)
Aggressive cows Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9218   Accepted: 4580 Description Farmer John has built a new long barn, with N (2 His C
POJ2481:Cows(树状数组)
Description Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good. 
文章热词 机器学习 机器学习课程 机器学习教程 深度学习视频教程 深度学习学习
相关热词 android模拟按home android 修改home键 android 截断home python教程+chm python教程百家号