洛谷 [P2349] 金字塔
洛谷 [P2349] 金字塔
洛谷【P2349】金字塔
有一盗墓者潜入一金字塔盗宝。当她（难道是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）秒。
输出格式：
输出所求的最少时间（单位为秒）。本题需要统计每条到达终点的路径，并在其中求出最大的一条边
解题
最后统计答案的时候只需要当前路径的长度+其中最大的一条边
公式：ans=max{dis[x]+maxedge[x]}ans= \max \{ dis[x]+maxedge[x]\}ans=max{dis[x]+ ...