Submit solution
Points:
1.29 (partial)
Time limit:
4.5s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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