#P3245. 最快路线
最快路线
最快路线
题目描述
小 R 从家所在的 号路口开往 号路口,希望用时最短。每条道路都是单向的。对于任意两个路口 和 ,从 到 至多有一条道路。
驶入有限速标志的道路时,小 R 按该路的限速行驶。若该路的限速标志丢失,则保持驶入前的速度。通过一条道路的时间等于道路长度除以行驶速度。在路口转弯和改变速度都可以瞬间完成。出发时的速度为 。
输入格式
第一行包含三个整数 ,分别表示路口数、道路数和目的地编号。路口编号为 至 。
接下来 行,每行包含四个整数 ,表示一条从路口 到路口 的道路,限速为 ,长度为 。若 ,表示该道路的限速标志丢失。
输出格式
输出一行,依次列出最快路线经过的路口编号,包括起点 和终点 。保证最快路线唯一。
样例 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
数据规模与约定
- 对于 的数据,。
- 对于所有数据,,,。