1199: 最快路线

精明的小R每每开车出行总是喜欢走最快路线,而不是最短路线.很明显,每条道路的限速是小R需要考虑的关键问题.不过有一些限速标志丢失了,于是小R将不知道能开多快.不过有一个合理的方法是进入这段道路时不改变速度行驶.你的任务就是计算从小R家($0$号路口)到$D$号路口的最快路线.

现在你得到了这个城市的地图,这个地图上的路都是单向的,而且对于两个路口$A$和$B$,最多只有一条道路从$A$到$B$.并且假设可以瞬间完成路口的转弯和加速.

第一行是三个整数$N,M,D$(路口数目,道路数目,和目的地). 路口由$0...N-1$标号

接下来$M$行，每行描述一条道路:有四个整数$A,B,V,L$,(起始路口,到达路口,限速,长度) 如果$V=0$说明这段路的限速标志丢失.

开始时你位于$0$号路口,速度为$70$.

仅仅一行,按顺序输出从$0$到$D$经过的城市.保证最快路线只有一条.

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\%$的数据 $N\le 20$

对于$100\%$的数据 $2\le N \le 150;0 \le V \le 500;1\le L\le 500$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！