VM 14 Bài 07 - SPEED

View as PDF

Submit solution

Points: 1.29 (partial)
Time limit: 4.5s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM14
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đất nước của ~w~ có ~V~ thành phố và ~E~ tuyến đường một chiều nối giữa các thành phố này. ~w~ đang ở thành phố ~1~ và muốn di chuyển tới thành phố ~V~ với vận tốc trung bình bé nhất có thể.

Bạn được cho biết thông tin về các con đường này: mỗi con đường sẽ được cho dưới dạng ~u~ ~v~ ~s~ t, trong đó ~u~ là điểm đầu, ~v~ là điểm cuối, ~s~ là độ dài con đường và ~t~ là thời gian cần để đi qua con đường đó (bạn không được đi chậm hơn vì sẽ gây cản trở tới giao thông trên các tuyến đường). Hãy giúp ~w~ tìm ra con đường có vận tốc trung bình bé nhất nhé!

Input

Dòng đầu tiên chứa ~2~ số ~V~ và ~E~.

~E~ dòng tiếp theo mỗi dòng chứa ~4~ số nguyên dương ~u~ ~v~ ~s~ t.

Output

  • Một số thực duy nhất là kết quả bài toán, in ra 6 chữ số sau dấu phẩy. Nếu không tồn tại đường đi in ra -1.

Giới hạn

  • ~V \leq 500~, ~E \leq 10^{4}~.
  • ~s~, ~t \leq 10^{8}~
  • Trong 50% số test: ~V \leq 100~, ~E \leq 1000~. ~s~, ~t \leq 100~.

Sample Input

4 4
1 2 2 1
1 3 3 2
2 4 5 3
3 4 5 4

Sample Output

1.333333314

Comments

Please read the guidelines before commenting.


There are no comments at the moment.