USACO 2019 - Dec - Gold - Milk Pumping


Submit solution

Points: 0.50
Time limit: 1.0s
Memory limit: 256M

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=969
Problem type

Gần đây người nông dân John đã quyết định mua một trang trại mới để mở rộng đế chế sữa của mình. Trang trại được kết nối với thị trấn gần đó bằng hệ thống các đường ống. John muốn tìm ra tập hợp các đường ống tối ưu nhất để bơm sữa từ trang trại tới thị trấn.

Một mạng lưới đường ống được biểu diễn bởi ~N~ giao điểm, đánh số từ ~1...N~. Giao điểm ~1~ là trang trại của John, còn giao điểm ~N~ là thị trấn. Có ~M~ đường ống hai chiều, mỗi đường ống kết nối hai giao điểm với nhau. Đường ống thứ ~i~ mất ~c_{i}~ chi phi để sử dụng và có lưu lượng là ~f_{i}~ lít sữa mỗi giây.

Nông dân John muốn tìm một con đường ống tối ưu nhất, điểm đầu là ~1~, điểm cuối là ~N~. Chi phí và lưu lượng của đường lần lượt là tổng chi phí và lưu lượng nhỏ nhất của các đường ống mà nó đi qua. Nông dân John muốn tìm một con đường sao cho biểu thức lưu lượng chia chi phí là nhỏ nhất. Dữ liệu đảm bảo có một đường đi từ ~1~ đến ~N~.

Input

  • Dòng đầu tiên ghi các số nguyên dương ~N~, ~M~ ~(2 \le N \le 1000, 1 \le M \le 1000)~.

  • ~M~ dòng tiếp theo, dòng thứ ~i~ biểu diễn đường ống thứ ~i~, kết nối hai giao điểm là ~a~, ~b~, mất chi phí là ~c_{ij}~, có lưu lượng là ~f_{ij}~.

Output

  • Gọi giá trị của đường đi có lưu lượng chia chi phí nhỏ nhất là: ~S~. In ra ~\left \lfloor{S \times 10^6}\right \rfloor~ (làm tròn xuống).

Sample Input

3 2
2 1 2 4
2 3 5 3

Sample Output

428571

Giới hạn:

  • Test 1 là test ví dụ.
  • Các tests 2-5 thoả mãn ~1 \le N, M \le 100~.
  • Các test còn lại có giới hạn gốc.

Note

  • Giải thích: chỉ có một con đường từ ~1~ tới ~N~. Nó có lưu lượng là ~min(3, 4) = 3~ và chi phí là ~2 + 5 = 7~.

Comments

There are no comments at the moment.