2 shunfurh shunfurh 于 2017.08.30 16:51 提问

Kingdom

King Kong is the feared but fair ruler of Transylvania. The king-dom consists of two cities and N < 150 towns, with nonin-tersecting roads between some of them. The roads are bidirectional, and it takes the same amount of time to travel them in both direc-tions. Kong has G < 353535 sol-diers.

Due to increased smuggling of goat cheese between the two cities, Kong has to place his sol-diers on some of the roads in such a way that it is impossible to go from one city to the other without pass-ing 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 ZIP-codes 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 phi, the time required to travel the road, phi < 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个回答

caozhy
caozhy   Ds   Rxr 2017.09.14 23:49
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Codeforces613D Kingdom and its Cities
Problem Codeforces Solution 套路虚树搞一下,然后我们考虑树形dp。 我们不妨设f[x]表示任意一个关键点都无法到达子树根的最小花费,g[x]表示允许有一个关键点到达子树根的最小花费。我们需要分情况进行讨论。 对于关键点,无法满足f[x]的情况,我们设成INF。而为了满足g[x],那么任意一个子树都无法到达其根,也不需要再砍断,即: f[x]=INFf[x...
Kingdom of Obsession
Kingdom of Obsession Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Problem Description There is a kindom of obsession, so people in this kingdom do thing
Kingdom uva+树状数组+并查集
Kingdom There were n cities in an ancient kingdom. In the beginning of the kingdom, all cities were isolated. Kings ordered their subjects to construct roads connecting cities. A lot of roads wer
HDU_1025Constructing Roads In JGShining's Kingdom
JGShining's kingdom consists of 2n(n is no more than 500,000) small cities which are located in two parallel lines. Half of these cities are rich in resource (we call them rich cities) while the ot
uva 1455 - Kingdom(并查集+线段树)
题目链接:uva 1455 - Kingdom 题目大意:平面上又n个城市,初始时城市之间没有任何双向道路相连,要求一次执行指令。 road A B :在城市A和城市B之间连接一条双向道路line C:询问一条y=C的水平线上穿过多少州和这些州总共有多少城市。 一个联通分量算一个州,C保证为小数部分为0.5的实数。 解题思路:线段树维护每个位置上州和城市的个数,并查集维护哪些城
Kingdom Rush Demo
kingdom rush demo source code
Kingdom Rush 1.07 破解版
Kingdom Rush 1.07 SWF破解版
破解Kingdom Rush:Frontiers
真是丢人,作为一个开发人员,尽然如此无视版权,舍不得花钱买游戏。通过越狱的手机,装了个游戏之后,玩儿得挺开心。还想着破解,人家付费购买的刀具,太小农了。 道貌岸然地反省一把之后,开始言归正传: 直接在cydia的源里面搜索关键字,可以找到这个游戏的hack插件,我试了一把,差不多都有效,什么金钱无限啊,什么双倍伤害啊。 唯独解锁英雄不好使,这怎么行呢,我就要这个功能啊,要别的功能也没
A. Help Far Away Kingdom
time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output In a far away kingdom lived the King, the Prince, the Shoemaker,
LA4730 Kingdom
1.题目描述:点击打开链接 2.解题思路:本题利用BIT+并查集解决。根据题意可以发现,x值是没有意义的,因此本题实际上是一维的一个操作题。由于line操作需要输出州的个数和城市的个数,且是统计一个点处的结果,自然可以想到用离线标记法来解决,又因为查询操作也比较多,因此可以用BIT来标记和查询。那么如何来更新一个州的城市数目呢?可以用并查集解决,但是有一个问题:两个连通分量合并成一个连通分量时候