#P1813. 拯救小 tim
拯救小 tim
题目描述
小 tim 在游乐场,有一天终于逃了出来!但是不小心又被游乐场的工作人员发现了…所以你的任务是安全地把小 tim 护送回家。但是,A 市复杂的交通状况给你出了一大难题。
A 市一共有 个路口, 条单行马路。但是,每条马路都只有一段时间是开放的。为了安全,你必须选择一条护送路线,使得小 tim 在路上的时间最短,即到家的时刻减去离开游乐场的时刻最短。
输入格式
第一行 个数,分别是 。基地在路口 ,码头在路口 。
接下来 行每行 个数 表示一条 路口到 路口的单行线,在 时刻到 时刻之间开放,需要 的时间通过这条路(必须保证行进在路中间时,路一直开放,否则小 tim 会被捉住)。两个路口之间可能会有多条道路。一开始的时刻是 (当然,你可以不用马上出发,在基地多呆一段时间)。
如果不存在任何一种方案使得小 tim 能成功到达码头,输出 Impossible
。
输出格式
一行,为小 tim 在路上停留的最短时间。
4 5 1 4
1 2 0 1 1
1 2 0 1 2
1 3 1 3 2
2 4 3 4 1
3 4 3 4 1
3
提示
【样例解释 #1】
最优方案应该是,在 号点停留至时刻 ,然后走到 号点,然后走到 号点。到达时刻为时刻 。tim 在路上的时间为 。
数据范围
对于所有测试数据:
- ,,,;
- ,,。