Thi thử Duyên hải 2021 - Lần 1 - Bài 5 - RUNNING

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

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

Vương quốc chuẩn bị tổ chức một cuộc thi chạy việt dã. Mạng lưới đường sá của vương quốc bao gồm ~n - 1~ đường hai chiều kết nối ~n~ tỉnh. Giữa hai tỉnh bất kì đều có thể đi đến được với nhau thông qua những con đường này. Cuộc thi chạy sẽ có điểm xuất phát là tỉnh ~A~ (kinh đô) và điểm đích là tỉnh ~B~ (cố đô).

Do công tác bảo trì đường sá không được quốc vương chú trọng, các con đường này đã xuống cấp trầm trọng. Nếu chỉ đi bộ thì không có vấn đề gì, tuy nhiên, đây lại là một cuộc thi chạy. Mỗi con đường chỉ có thể chịu được một số lượng người nhất định chạy qua nó mà thôi.

Quốc vương vì muốn nhiều người được tham gia cuộc thi chạy nhất nên quyết định xây thêm một con đường mới (với chất lượng rất tốt, bao nhiêu người chạy qua cũng không hỏng). Tuy nhiên, con đường này không được phép nối trực tiếp đến kinh đô và cũng không được phép nối trực tiếp đến cố đô. Hãy giúp quốc vương tính xem sau khi xây dựng con đường mới, sẽ có tối đa bao nhiêu người có thể tham gia vào cuộc thi chạy?

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~A~ và ~B~ ~(4 \leq n \leq 100000~; ~1 \leq A~, ~B \leq n~; ~A \leq B)~.

~n~ - ~1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~ và ~c~ ~(1 \leq u~, ~v \leq n~; ~u \leq v~; ~1 \leq c \leq 1000)~ cho biết có một con đường hai chiều nối hai tỉnh ~u~ và ~v~, có tối đa ~c~ người có thể chạy qua con đường này.

Output

In ra số lượng tối đa người có thể tham gia cuộc thi chạy sau khi quốc vương xây thêm một con đường mới.

Sample Input

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

Sample Output

15

Note

Đề gốc thi thử duyên hải 2021 lần 1


Comments

Please read the guidelines before commenting.



  • 0
    I_love_Hoang_Yen   commented on April 23, 2021, 9:37 p.m.

    Bộ test thiếu trường hợp:

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