Bảo vệ

View as PDF
Submit solution
Points: 0.22 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một mạng lưới gồm ~N~ thành phố, và một số đường một chiều nối các cặp thành phố (giữa hai thành phố có thể có nhiều đường nối một chiều).

Quân địch đang tập trung ở thành phố ~N~, định tiến công ta ở thành phố ~1~, và chúng sẽ tiến công trên tất cả các con đường chưa được bảo vệ để tiến vào thành phố ~1~. Bộ chỉ huy ta cần xác định số quân ít nhất trên các con đường để chặn địch tiến về thành phố ~1~.

Input

Dòng đầu ghi ~N~ ~\left(N \leq 5000\right)~.

Các dòng tiếp theo cho đến hết file có không quá ~10000~ dòng, mỗi dòng một tả ~1~ đường gồm ~u, v, s~ cho biết có đoạn đường một chiều từ ~u~ đến ~v~, và phải cần ít nhất ~s~ ~\left(s \leq 65000\right)~ quân để chặn địch trên đường này.

Output

Số quân ít nhất cần điều động.

Sample Input

10
10 7 25050
6 1 12564
10 4 23916
5 1 61054
10 9 50950
9 1 35558
10 2 60941
3 1 22203
8 2 2853
5 7 31422
3 7 41491
8 7 27235
4 8 55965
8 6 41980
3 6 47707
2 3 45320
3 8 11237
7 6 38734
5 6 7561
3 5 8844

Sample Output

79169

Comments

Please read the guidelines before commenting.


  • -11
    hmackervjppro  commented on Oct. 17, 2023, 2:26 p.m.

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


  • 3
    mhdttq  commented on Nov. 12, 2021, 2:54 p.m.

    bài này rất hay