TAITRONG - Tải trọng tuyến đường (Olympic 30/4 XXII Khối 10)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Một hệ thống giao thông gồm n thành phố được đánh số từ 1 đến n. Hệ thống giao thông có m đoạn đường hai chiều nối giữa các thành phố. Mỗi đoạn đường có một trọng tải tối đa là z, cho biết các xe với tải trọng không lớn hơn z mới lưu thông được trên con đường đó.

Yêu cầu: Cho trước tải trọng của các đoạn đường trong hệ thống giao thông. Hãy tìm một hành trình từ thành phố s đến thành phố t sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể được.

Dữ liệu vào:

  • Dòng thứ nhất ghi 4 số nguyên n, m, s, t (2 <= n <= 103; 1 <= m <= 104; 1 <= s, t <= n; s khác t)
  • Tiếp theo là m dòng, mỗi dòng ghi ba số nguyên x, y, z với ý nghĩa có đoạn đường đi giữa thành phố x và thành phố y với tải trọng tối đa là z (1 <= z <= 105).

          Các số ghi trên cùng một dòng cách nhau ít nhất một kí tự trắng.

Kết quả: Gồm 1 dòng ghi số nguyên là tải trọng lớn nhất cần tìm, nếu không có ghi -1.

 

Ví dụ

  • input
    4 5 1 4
    1 2 10
    2 4 1
    1 3 5
    3 4 3
    1 4 2
    output
    3
Back to Top