Dotcpp  >  编程题库  >  Repairing a Road
题目 1078:

Repairing a Road

时间限制: 2s 内存限制: 192MB 提交: 446 解决: 259

题目描述

You live in a small town with R bidirectional roads connecting C crossings and you want to go from crossing 1 to crossing C as soon as possible. You can visit other crossings before arriving at crossing C, but it’s not mandatory.

You have exactly one chance to ask your friend to repair exactly one existing road, from the time you leave crossing 1. If he repairs the i-th road for t units of time, the crossing time after that would be viai-t. It's not difficult to see that it takes vi units of time to cross that road if your friend doesn’t repair it.

You cannot start to cross the road when your friend is repairing it.

输入格式

 There will be at most 25 test cases. Each test case begins with two integers C and R (2<=C<=100, 1<=R<=500). Each of the next R lines contains two integers xiyi (1<=xiyi<=C) and two positive floating-point numbers vi and ai (1<=vi<=20,1<=ai<=5), indicating that there is a bidirectional road connecting crossing xi and yi, with parameters vi and ai (see above). Each pair of crossings can be connected by at most one road. The input is terminated by a test case with C=R=0, you should not process it.

输出格式

 For each test case, print the smallest time it takes to reach crossing C from crossing 1rounded to digitsafter decimal point. It’s always possible to reach crossing C from crossing 1.

样例输入

3 2
1 2 1.5 1.8
2 3 2.0 1.5
2 1
1 2 2.0 1.8
0 0

样例输出

2.589
1.976

提示

零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情
标签