Olympic 30/4 2016 - Khối 10 - Bài 2 - Tải trọng tuyến đường

View as PDF
Submit solution
Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: TAITRONG.INP
Output: TAITRONG.OUT
Problem source:
Olympic 30/4
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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ố (giữa hai thành phố bất kỳ luôn có đường đi). Mỗi đoạn đường có một tải trọng 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ể.

Input

Cho từ tệp văn bản TAITRONG.INP gồm:

  • Dòng thứ nhất ghi ~4~ số nguyên ~n,\ m,\ s,\ t~ ~(2\le n \le 10^3;\ 1\le m \le 10^4;\ 1\le s,\ t\le n; s\ne t)~.

  • Tiếp theo là ~m~ dòng, mỗi dòng ghi ~3~ số nguyên ~x,\ y,\ z~ với ý nghĩa có đoạn đường giữa thành phố ~x~ và thành phố ~y~ với tải trọng tối đa cho phép là ~z~ ~(1 \le z \le 10^4)~.

    Các số trên cùng dòng viết cách nhau bởi ít nhất một dấu cách.

Output

Ghi vào tệp văn bản TAITRONG.OUT gồm một dòng ghi số nguyên là tải trọng lớn nhất cần tìm.

Scoring

~50\%~ số test tương ứng với ~50\%~ số điểm của bài có ~2\le n \le 100~.

Sample Input 1

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

Sample Output 1

3

Comments

Please read the guidelines before commenting.


  • -9
    THPTHD_Hieu  commented on May 12, 2025, 7:30 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -2
      RussVN123  commented on May 13, 2025, 6:42 a.m.

      Gà chiến !


      • -3
        THPTHD_Hieu  commented on May 13, 2025, 8:11 a.m.

        Hiếu chiến !


  • -2
    vendettas  commented on April 6, 2025, 5:41 a.m.

    um nha anh trong mit thai


    • -2
      phanmd  commented on April 6, 2025, 8:46 a.m.

      Không kể thì im lặng


  • -16
    gv_THCSgiaphu_Vuhuuphong  commented on March 19, 2024, 8:35 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.