#P1813. 拯救小 tim

拯救小 tim

题目描述

小 tim 在游乐场,有一天终于逃了出来!但是不小心又被游乐场的工作人员发现了…所以你的任务是安全地把小 tim 护送回家。但是,A 市复杂的交通状况给你出了一大难题。

A 市一共有 nn 个路口,mm 条单行马路。但是,每条马路都只有一段时间是开放的。为了安全,你必须选择一条护送路线,使得小 tim 在路上的时间最短,即到家的时刻减去离开游乐场的时刻最短。

输入格式

第一行 44 个数,分别是 n,m,s,tn,m,s,t。基地在路口 ss,码头在路口 tt

接下来 mm 行每行 55 个数 x,y,b,e,cx,y,b,e,c 表示一条 xx 路口到 yy 路口的单行线,在 bb 时刻到 ee 时刻之间开放,需要 cc 的时间通过这条路(必须保证行进在路中间时,路一直开放,否则小 tim 会被捉住)。两个路口之间可能会有多条道路。一开始的时刻是 00(当然,你可以不用马上出发,在基地多呆一段时间)。

如果不存在任何一种方案使得小 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】

最优方案应该是,在 11 号点停留至时刻 11,然后走到 33 号点,然后走到 44 号点。到达时刻为时刻 44。tim 在路上的时间为 41=34-1=3

数据范围

对于所有测试数据:

  • 2n1002\leqslant n\leqslant1000m10000\leqslant m\leqslant10001s,tn1\leqslant s,t\leqslant nsts\not=t
  • 1x,yn1\leqslant x,y\leqslant n0b,e,c100000\leqslant b,e,c\leqslant10000b<eb<e