Bảo vệ
Xem dạng PDF
Gửi bài giải
Điểm:
0,22 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
bài này rất hay