提交: 48 解决: 14

[提交] [状态] [讨论版] [命题人:]

题目描述

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

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 *x*_{i}, *y*_{i} (1<=*x*_{i}, *y*_{i}<=C) and two positive floating-point numbers *v*_{i} and *a*_{i} (1<=*v*_{i}<=20,1<=*a*_{i}<=5), indicating that there is a bidirectional road connecting crossing *x*_{i} and *y*_{i}, with parameters *v*_{i} and *a*_{i} (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 1, rounded to 3 digits after decimal point. It’s always possible to reach crossing *C* from crossing 1.

样例输入
Copy

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

样例输出 Copy

```
2.589
1.976
```

来源/分类