BZPRO

#1376. [Baltic2002]limit 速度限制

内存限制：64 MiB 时间限制：5 Sec
提交 提交记录 讨论

题目描述

在生活中,我们经常选择最快的路线.开车时每条道路的速度限制在为最关键的问题,不幸的是有些限速的标志丢失了. 因此你无法知道应该开多快,一种可以详解的解决方案是:按照原来的速度行驶,你的任务是计算两地间的最快路线. 现在给出地图来,其只包括N个路口(2<=N<=150,编号从0到N-1).和M条路来,道路是双向的,最多只有一条路从A到B. 你可以假设加速不要时间,且不会有交通堵塞.当然你的车速不能超过当前速度限制,注意开始时你在0点,速度为70

输入格式

输出格式

样例

样例输入


			
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

数据范围与提示

保证答案唯一

BZPRO Powered by Remmina.
Github Repository