Til the Cows Come Home
Time Limit:1000MS |
|
Memory Limit:65536K |
Total Submissions:13050 |
|
Accepted:4261 |
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
无向图的最短路径,求1到N的最短路径
分享到:
相关推荐
北大POJ1062-Expensive dowry【dijkstra】 解题报告+AC代码
dijkstra 算法 需要考虑重边.........
poj1007 AC代码 0MS过题写法 不过是个水题 哈哈哈哈
这题是道神题,神就神在,它既能让你搞懂网络流及其优化,还给了你很大的优化空间。
poj 3674 SuperAssassin 的AC代码
poj习题第一题,很有意思,是学习poj的开始
我的Poj里的一些AC代码
POJ 1328 java做!雷达问题!java版本!AC答案~
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-所有题目AC代码+解题报告
poj1009 Edge Detection 可以直接AC的
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。
poj3586,推导题,可以推导出一个贪心的结论,具体看代码。
解决poj1006问题
http://acm.pku.edu.cn/JudgeOnline/ acm的AC解题报告
一年多的ACM经历,做了这300多题,希望对大家有帮助!!
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
北大POJ1159-Palindrome 解题报告+AC代码