• [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暑期集训出题练习
  • 操作

显示春菜