2683: 拯救小 tim
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
小 tim 在游乐场,有一天终于逃了出来!但是不小心又被游乐场的工作人员发现了。。。
所以你的任务是安全地把小 tim 护送回家。但是,A 市复杂的交通状况给你除了一个难题。A 市一共有 n 个路口,m 条单行马路。但是,每条马路都只有一段时间是开放的。为了安全,你必须选择一条护送路线,使得小 tim 在路上的时间最短,即到家的时刻减去离开游乐场的时刻最短。
输入
第一行 4 个数,分别是 n,m,s,t(2<=n<=100;0<=m<=1000;1<=s,t<=n,s≠t)。基地在路口s,码头在路口 t。
接下来 m 行每行 5 个数 x,y,b,e,c 表示一条 x 路口到 y 路口的单行线,在 b 时刻到e 时刻之间开放,需要 c 的时间通过这条路(必须保证行进在路中间时,路一直开放,否则
小 tim 会被捉住)。两个路口之间可能会有多条道路。一开始的时刻是 0(当然,你可以不用马上出发,在基地多呆一段时间)。
如果不存在任何一种方案使得小 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 号点停留至时刻 1,然后走到 3 号点,然后走到 4 号点。到达时刻为时刻 4。在路上的时间为 4-1=3。