NKZX_NOI_OJ discuss3

题目描述

有一个旅行者计划乘马车旅行，他的出发点和目的地是固定的，但不能确定路线。全国的城市有一个公路网，若在两个城市之间有一条路，则可以坐公共马车从一个城市到另一个城市。乘马车需要一张票，在每张票上都注明了马的数量。当然，马越多，马车跑得越快。在出发点，旅行者有许多车票。通过考虑这些车票和道路网络上的信息，我们应该能找到在最短时间内把他带到目的地的最佳路线。应考虑怎样使用车票，假设以下条件：①乘马车可以把旅行者从一个城市直接带到另一个通过公路相连的城市。换而言之，每到一个城市，他都必须换车；②在通过公路直接连接的两个城市之间只可以使用一张车票；③每张车票都只可以使用一次；④乘马车所需的时间是两个城市之间的距离除以马的数量；⑤应忽略换乘所需的时间。

输入

输入由多个数据集组成，每个数据集的格式如下。在最后一个数据集后面是一行，包含5个0（用空格分隔）。
n m p a b
t1 t2 ... tn
x1 y1 z1
x2 y2 z2
...
xp yp zp

数据集中的每个输入项都是非负整数。n 是长途汽车票的数量，1≤n ≤8；m 是城市数，2≤m ≤30；p 是道路数，可能为0；a 是起始城市的编号，b 是目的地城市的编号，a ≠b 。所有城市的编号都为1～m 。第2行给出了车票信息，ti 是第i 张车票的马数（1≤i ≤n，1≤ti≤10）。以下p 行给出城市之间的道路信息。第i 条道路将两个城市 xi 和 yi 连接起来，并有距离 zi （ 1≤i ≤p ， 1≤zi≤100）。两个城市之间最多一条道路，一条路不会连接城市自己，每条路都可双向行驶。

输出

若旅行者可以到达目的地，则输出出发点到目的地的最短时间。答案的误差不应大于0.001。在满足上述精度条件的前提下，可以输出小数点后的任意位数。若无法到达目的地，则输出“Impossible”。

样例输入 Copy

3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

样例输出 Copy

30.000
3.667
Impossible
Impossible
2.856

来源/分类

动态规划算法状压DP

2144: 马车旅行（POJ2686）

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

来源/分类