#P2349. 金字塔
金字塔
题目描述
有一盗墓者潜入一金字塔盗宝。当她(难道是 Lara Croft ?)打开一个宝箱的时候,突然冒出一阵烟(潘多拉的盒子?),她迅速意识到形势不妙,三十六计走为上计……由于她盗得了金字塔的地图,所以她希望能找出最佳逃跑路线。地图上标有 个室,她现在就在 室,金字塔的出口在 室。她知道一个秘密:那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线,使得在最坏的情况下所用的时间最少。
输入格式
输入文件的第一行有两个正整数 ()和 ();下面有 行,每行有三个数正整数 、 、 ,表示直接从 室跑到 室( 室跑到 室)需要 ()秒。
输出格式
输出所求的最少时间(单位为秒)。
7 8
1 2 10
2 3 12
3 4 20
4 7 8
1 7 34
2 5 10
5 6 12
6 4 13
66
提示
样例解释 Sample Explan:
基本上有三种路线:
(1)。
总时间为: + + + = ,最坏的情况是“ ”那一段,要多花 秒(因为行走速度减半),所以这条路选最坏需要 秒;
(2)。
总时间为: + + + + = ,最坏的情况是“ ”那一段,要多花 秒,所以这条路选最坏需要 秒;
(3)。
总时间为: = ,最坏的情况是“ ”那一段,要多花 秒,所以这条路选最坏需要 秒。