编程介的小学生 2018-11-14 02:44 采纳率: 0.4%
浏览 495
已采纳

图论搜索——如何遍历搜索这个图的算法

Problem Description
King Kong is the feared but fair ruler of Transylvania. The kingdom consists of two cities and N < 150 towns, with nonintersecting roads between some of them. The roads are bidirectional, and it takes the same amount of time to travel them in both directions. Kong has G < 353535 soldiers.
Due to increased smuggling of goat cheese between the two cities, Kong has to place his soldiers on some of the roads in such a way that it is impossible to go from one city to the other without passing a soldier. The soldiers must not be placed inside a town, but may be placed on a road, as close as Kong wishes, to any town. Any number of soldiers may be placed on the same road. However, should any of the two cities be attacked by a foreign army, the king must be able to move all his soldiers fast to the attacked city. Help him place the soldiers in such a way that this mobilizing time is minimized.
Note that the soldiers cannot be placed in any of the cities or towns. The cities have ZIP-codes 95050 and 104729, whereas the towns have ZIPcodes from 0 to N - 1. There will be at most one road between any given pair of towns or cities.

Input
The input contains several test cases. The first line of each test case is N, G and E, where N and G are as defined above and E < 5000 is the number of roads. Then follow E lines, each of which contains three integers: A and B, the ZIP codes of the endpoints, and φ, the time required to travel the road,φ < 1000. The last line of the input is a line containing a single 0.

Output
For each test case in the input, print the best mobilizing time possible, with one decimal. If the given number of soldiers is not enough to stop the goat cheese, print "Impossible" instead.

Sample Input
4 2 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
4 1 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
4 2 7
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
2 1 5
0

Sample Output
2.5
Impossible
3.0

展开全部

  • 写回答

1条回答 默认 最新

  • threenewbee 2018-12-09 04:35
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥20 有人知道这是什么问题吗
  • ¥15 torch框架下的强化学习DQN训练奖励值浮动过低,希望指导如何调整
  • ¥35 西门子博图v16安装密钥提示CryptAcquireContext MS_DEF_PROV Error of containger opening
  • ¥15 mes系统扫码追溯功能
  • ¥40 selenium访问信用中国
  • ¥20 在搭建fabric网络过程中遇到“无法使用新的生命周期”的报错
  • ¥15 Python中关于代码运行报错的问题
  • ¥500 python 的API,有酬谢
  • ¥15 软件冲突问题,软件残留问题
  • ¥30 有没有人会写hLDA,有偿求写,我有一个文档,想通过hLDA得出这个文档的层次主题,有偿有偿!
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部