• [1728] 神庙逃亡

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 在一次探险中,吴邪无意进入了一个迷宫并触发了机关,
    他要在一定时间内赶快找到出口并逃离,否则会被机关
    杀死。现在他发现了一个迷宫的地图,他知道了迷宫内
    有多少个路口和每条路的情况。但他发现要想从出口出
    去必须去一个地方拿到钥匙(有且只有一个钥匙)。为了
    活下去,他现在必须找到一条耗时最短的路逃离。你现
    在需要知道他能不能活着出去。
  • 输入
  • 第一行一个整数,表示有T(1<=T<=100)组数据。
    第二行输入n,m,s,l,v,分别表示迷宫中有多少路口、道路
    、入口、出口和吴邪有多少时间。
    接下来m行输入x,y,t,a。(题中数据均为整数,n<=10^3,
    m<=10^4,1<=v<=50,1<=s,l,a<=n)a为0表示y处没
    又钥匙,a为1有钥匙。
  • 输出
  • 对于每组数据输出一行表示吴邪有没有活下来,如果活
    下来输出他花费最少的时间,如果没活下来输出-1.
  • 样例输入
  • 1
    5 7 1 5 10
    1 2 3 0
    1 3 4 1
    1 4 5 0
    2 3 2 1
    3 4 6 0
    3 5 4 0
    4 5 5 0
  • 样例输出
  • 8
  • 提示
  • 来源
  • 2018暑期集训出题练习
  • 操作

显示春菜