3. 速度限制
【问题描述】
在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可行的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。
你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地A和B，最多只有一条道路从A连接到B。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。
【文件输入】
输入文件speed.in 的第一行是3个整数N，M和D(2<＝N<=150)，N表示城市的数目，用0..N-1标记。M是道路的总数，D表示你的目的地。接下来的M行，每行描述一条道路，每行有4个整数A(0≤A<N)，B(0≤B<N)，V(0≤V≤500)和 L(1≤L≤500)，这条路是从A到B的，速度限制是V，长度为L。如果V是0，表示这条路的限速未知。如果V不为0，则经过该路的时间T=L/V。否则T=L/Vold，Vold是你到达该路口前的速度。开始时你位于0点，并且速度为70。
【文件输出】
输出文件speed.out仅一行整数，表示从0到D经过的城市。
输出的顺序必须按照你经过这些城市的顺序，以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
首先，利用预处理计算任意两个节点之间只经过无限速标志的路的最短距离。这可以用F1oyd算法得到，时间复杂度为O(n3)。
计算城市1到城市D之间最快路径时，只需对Dijkstra稍作修改即可：在Dijkstra算法中，用一个已计算出最短时间的节点去刷新其他节点当前最短时间时，除了要枚举有限速标志的路以外，还要在此路的基础上，枚举通过此路后要经过无限速标志的路到达的节点。时间复杂度为O(n2+mn)，即O(mn)。