ZZULIOJ - 18新利直播

题目描述

You live in a small town withRbidirectional roads connectingCcrossings and you want togofrom crossing 1 to crossingCas soon as possible. You can visit other crossings before arriving at crossing C, but it’s not mandatory.

You haveexactly onechance to ask your friend to repair exactly one existing road,from the time youleavecrossing 1. If he repairs thei-th road fortunits of time, the crossing time after that would bev_ia_i^-t. It's not difficult to see that it takesv_iunits of time to cross thatroad 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 integersCandR(2<=C<=100, 1<=R<=500). Each of the nextRlines contains two integersx_i,y_i(1<=x_i,y_i<=C) and two positive floating-point numbersv_ianda_i(1<=v_i<=20,1<=a_i<=5), indicating that there is a bidirectional road connecting crossingx_iandy_i, with parametersv_ianda_i(see above). Each pair of crossings can be connected by at most one road. The input is terminated by a test case withC=R=0, you should not process it.

输出

For each test case, print the smallest time it takes to reach crossingCfrom crossing 1, rounded to 3 digits after decimal point. It’s always possible to reach crossingCfrom 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

问题 G: Repairing a Road