P2349 金字塔

有一盗墓者潜入一金字塔盗宝。当她（难道是 Lara Croft ?）打开一个宝箱的时候，突然冒出一阵烟（潘多拉的盒子？），她迅速意识到形势不妙，三十六计走为上计……由于她盗得了金字塔的地图，所以她希望能找出最佳逃跑路线。地图上标有 $N$ 个室，她现在就在 $1$ 室，金字塔的出口在 $N$ 室。她知道一个秘密：那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线，使得在最坏的情况下所用的时间最少。

无

无

样例解释 Sample Explan： 基本上有三种路线： （1）$1 \to 2 \to 3 \to 4 \to 7$。 总时间为：$10$ ＋ $12$ ＋ $20$ ＋ $8$ ＝ $50$，最坏的情况是“ $3 \to 4$ ”那一段，要多花 $20$ 秒（因为行走速度减半），所以这条路选最坏需要 $70$ 秒； （2）$1 \to 2 \to 5 \to 6 \to 4 \to 7$。 总时间为：$10$ ＋ $10$ ＋ $12$ ＋ $13$ ＋ $8$ ＝ $53$，最坏的情况是“ $6 \to 4$ ”那一段，要多花 $13$ 秒，所以这条路选最坏需要 $66$ 秒； （3）$1 \to 7$。 总时间为：$34$ ＝ $34$，最坏的情况是“ $1 \to 7$ ”那一段，要多花 $34$ 秒，所以这条路选最坏需要 $68$ 秒。