#P3245. 最快路线

    ID: 2430 传统题 1000ms 512MiB 尝试: 309 已通过: 120 难度: 5 上传者: 标签>难度分类普及+/提高-图论状态扩展图Dijkstra枚举与搜索路径恢复数据结构懒删除CF1700

最快路线

最快路线

题目描述

小 R 从家所在的 00 号路口开往 DD 号路口,希望用时最短。每条道路都是单向的。对于任意两个路口 AA 和 BB,从 AA 到 BB 至多有一条道路。

驶入有限速标志的道路时,小 R 按该路的限速行驶。若该路的限速标志丢失,则保持驶入前的速度。通过一条道路的时间等于道路长度除以行驶速度。在路口转弯和改变速度都可以瞬间完成。出发时的速度为 7070。

输入格式

第一行包含三个整数 N,M,DN,M,D,分别表示路口数、道路数和目的地编号。路口编号为 00 至 N−1N-1。

接下来 MM 行,每行包含四个整数 A,B,V,LA,B,V,L,表示一条从路口 AA 到路口 BB 的道路,限速为 VV,长度为 LL。若 V=0V=0,表示该道路的限速标志丢失。

输出格式

输出一行,依次列出最快路线经过的路口编号,包括起点 00 和终点 DD。保证最快路线唯一。

样例 1

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40
0 5 2 3 1

数据规模与约定

  • 对于 30%30\% 的数据,N≤20N\le 20。
  • 对于所有数据,2≤N≤1502\le N\le 150,0≤V≤5000\le V\le 500,1≤L≤5001\le L\le 500。