华师一附中OI组
标题:
2721 金字塔
[打印本页]
作者:
admin
时间:
2021-10-19 18:18
标题:
2721 金字塔
问题描述:
有一盗墓者潜入一金字塔盗宝。当她(难道是Lara Croft ?)打开一个宝箱的时候,突然冒出一阵烟(潘多拉的盒子?),她迅速意识到形势不妙,三十六计走为上计…… 由于她盗得了金字塔的地图,所以她希望能找出最佳逃跑路线。地图上标有N个室,她现在就在1室,金字塔的出口在N室。她知道一个秘密:那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线,使得在最坏的情况下所用的时间最少。
输入格式:
从文件PYRAMID.INP读入数据,文件第一行有两个正整数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 秒
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2