#5036. 速度限制

速度限制

题目描述

在这个繁忙的社会中,我们往往不再去选择最短的道路,而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是,有一些限速的标志丢失了,因此你无法得知应该开多快。一种可以辩解的解决方案是,按照原来的速度行驶。你的任务是计算两地间的最快路线。

你将获得一份现代化城市的道路交通信息。为了使问题简化,地图只包括路口和道路。每条道路是有向的,只连接了两条道路,并且最多只有一块限速标志,位于路的起点。两地 AABB,最多只有一条道路从 AA 连接到 BB。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然,你的车速不能超过当前的速度限制。

输入格式

第一行是 33 个整数 NNMMDD (2N1502\leq N\leq 150),表示道路的数目,用 0 N10 ~ N-1 标记。MM 是道路的总数,DD 表示你的目的地。

接下来的 MM 行,每行描述一条道路,每行有 44 个整数 AA (0A<N0\leq A<N),BB (0B<N0\leq B<N),VV (0V5000\leq V\leq 500) 和 LL (1L5001\leq L\leq 500),这条路是从 AABB 的,速度限制是 VV,长度为 LL。如果 VV00,表示这条路的限速未知。

如果 VV 不为 00,则经过该路的时间 T=LVT=\frac{L}{V}。否则 T=LVoldT=\frac{L}{\text{Vold}}Vold\text{Vold} 是你到达该路口前的速度。开始时你位于 00 点,并且速度为 7070

输出格式

输出文件仅一行整数,表示从 00DD 经过的城市。

输出的顺序必须按照你经过这些城市的顺序,以 00 开始,以 DD 结束。仅有一条最快路线。

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