UVA1518 火车延误 Train delays

### 题目背景 无 有一群人（原文为judges,我不确定指的是谁，但不影响做题，所以暂称一群人。）要去某个地方旅行，他们上一次去的时候晚了很长时间，原因是火车老是晚到目的地。所以这次他们规划得很周密。他们仔细分析了列车时刻表，记录了火车延误的频率和延误的程度。既然他们知道了这些，他们就希望尽量缩短旅行的预期时间。 他们知道对于每一个列车连接点，其预定的发车时间和持续时间。以及其到达目的地延迟的概率。列车延误的可能性是不受其他列车干扰的。他们可以根据自己的行程进行调整，取决于他们可能已经发生的任何延误。火车总是准时发车，但是可能会晚点到达，而评委们不知道火车是否会晚点到登上它评委们没时间换车，所以在他们到达一个地方的同时他们可以坐一辆开走的转车。 他们可以自己选择出发的时间，并且他们希望尽可能减少预期的他们的总行程的持续时间（根据之前的连接和延误，给定一个列车要乘坐的旅行计划，预期的旅行持续时间e被定义为我可能乘坐的每一个行程的旅行持续时间t[i]之和乘以行程的概率p[i]发生：e=∑i p[i] t[i]）。

无

无