1557: 金字塔
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：49
解决：14
题目描述
有一盗墓者潜入一金字塔盗宝。当她（难道是Lara Croft ?）打开一个宝箱的时候，突然冒出一阵烟（潘多拉的盒子？），她迅速意识到形势不妙，三十六计走为上计…… 由于她盗得了金字塔的地图，所以她希望能找出最佳逃跑路线。地图上标有N个室，她现在就在1室，金字塔的出口在N室。她知道一个秘密：那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线，使得在最坏的情况下所用的时间最少。
输入
第一行有两个正整数N（3 ≤ N ≤ 100）和M（3 ≤ M ≤ 2000），
下面有M行，每行有三个数正整数U、V、W，
表示直接从U室跑到V室（V室跑到U室）需要W（3 ≤ W ≤ 255）秒。
输出
输出所求的最少时间（单位为秒）。
样例输入 复制
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提示
基本上有三种路线：
一：1 -> 2 -> 3 -> 4 -> 7 总时间为 10 + 12 + 20 + 8 = 50，最坏的情况是 3->4 那一段，要多花20秒（因为行走速度减半），所以这条路选最坏需要 70 秒
二：1 -> 2 -> 5 -> 6 -> 4 -> 7 总时间为 10 + 10 + 12 + 13 + 8 = 53，最坏的情况是 6->4 那一段，要多花13秒（因为行走速度减半），所以这条路选最坏需要 66 秒
三：1 -> 7 总时间为 34 = 34，最坏的情况是 1->7 那一段，要多花34秒（因为行走速度减半），所以这条路选最坏需要 68 秒
一：1 -> 2 -> 3 -> 4 -> 7 总时间为 10 + 12 + 20 + 8 = 50，最坏的情况是 3->4 那一段，要多花20秒（因为行走速度减半），所以这条路选最坏需要 70 秒
二：1 -> 2 -> 5 -> 6 -> 4 -> 7 总时间为 10 + 10 + 12 + 13 + 8 = 53，最坏的情况是 6->4 那一段，要多花13秒（因为行走速度减半），所以这条路选最坏需要 66 秒
三：1 -> 7 总时间为 34 = 34，最坏的情况是 1->7 那一段，要多花34秒（因为行走速度减半），所以这条路选最坏需要 68 秒