火车延误 Train delays

### 题目背景 无 ### 题目描述 有一群人（原文为judges,我不确定指的是谁，但不影响做题，所以暂称一群人。）要去某个地方旅行，他们上一次去的时候晚了很长时间，原因是火车老是晚到目的地。所以这次他们规划得很周密。他们仔细分析了列车时刻表，记录了火车延误的频率和延误的程度。既然他们知道了这些，他们就希望尽量缩短旅行的预期时间。 他们知道对于每一个列车连接点，其预定的发车时间和持续时间。以及其到达目的地延迟的概率。列车延误的可能性是不受其他列车干扰的。他们可以根据自己的行程进行调整，取决于他们可能已经发生的任何延误。火车总是准时发车，但是可能会晚点到达，而评委们不知道火车是否会晚点到登上它评委们没时间换车，所以在他们到达一个地方的同时他们可以坐一辆开走的转车。 他们可以自己选择出发的时间，并且他们希望尽可能减少预期的他们的总行程的持续时间（根据之前的连接和延误，给定一个列车要乘坐的旅行计划，预期的旅行持续时间e被定义为我可能乘坐的每一个行程的旅行持续时间t[i]之和乘以行程的概率p[i]发生：e=∑i p[i] t[i]）。 ### 输入输出格式 输入格式 在第一行是一个正整数：测试数据的组数。 下一行是出发的地点和目的地，它们是不同的。 再下一行是n(1<=n<=1000)，表示有几列火车。 然后是n行，这几列火车的信息： 先输入列车出发的地点和目的地，它们是不同的。 然后是一个整数m(0<=m<=59) 每小时后的发车时间（分钟） 然后是一个整数t(1<=t<=300) 标准行程时间（假设没有延误）。 然后是一个整数p (0 ≤ p ≤ 100) 以百分比表示的延迟概率 然后是一个整数 d(1<=d<=120) 最大延迟时间（分钟） 所有地名都以字符串的形式给出，字符串的长度为 最多20个。如果火车晚点了，那么晚点的长度将是整分钟，并且在[1，d]范围内。 输出格式 每个测试样例： 带浮点数的一行：总行程的最小预期持续时间（分钟）。 这个数字应该精确到10^(-6) 相对或绝对精度。输 出“IMPOSSIBLE”如果无法到达目的地。 请注意，在第一个例子中，最好从汉堡坐慢车到不莱梅，因为快车预计行程时间为70.25分钟。 ### 样例输入 ``` 3 Hamburg Bremen 3 Hamburg Bremen 15 68 10 5 Hamburg Bremen 46 55 50 60 Bremen Frankfurt 14 226 10 120 Amsterdam Rotterdam 1 Amsterdam Utrecht 10 22 5 10 BremenVegesack Utrecht 9 BremenVegesack BremenHbf 15 10 0 1 BremenVegesack BremenHbf 45 10 0 1 BremenVegesack Leer 23 140 10 15 BremenHbf Osnabruck 44 51 60 70 Osnabruck Amersfoort 55 147 38 40 Amersfoort Utrecht 24 15 30 15 Amersfoort Utrecht 54 15 10 35 Leer Groningen 45 140 5 10 Groningen Amersfoort 46 96 10 20 ``` ### 样例输出 ``` 68.3 IMPOSSIBLE 305.0532857 ```

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4264 [PDF](https://uva.onlinejudge.org/external/15/p1518.pdf)