P1813 拯救小tim_NOI导刊2011提高(02)

    • 63通过
    • 285提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    输入输出格式

    输入格式:

    第一行4个数,分别是n,m,s,t(2≤n≤100;0≤m≤l000;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在路上停留的最短时间。

    输入输出样例

    输入样例#1: 复制
    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 
    输出样例#1: 复制
    3

    说明

    【样例解释】 

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。