| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P145SUMH - ROUND 5H - Hệ thống điện |
Khu vực nhà Tí bị mất điện dài ngày để khắc phục sự cố đường dây 500 kV. Các kỹ sư bảo rằng khu vực này có khi mất điện đến cả tháng trời. Vì vậy, các hộ dân ở đây đã sử dụng máy phát điện. Không phải hộ gia đình nào cũng có, vì vậy, họ đã kết nối với nhau để tạo thành hệ thống lưới điện riêng. Rõ ràng những gia đình nào ở càng xa nguồn phát thì điện sẽ càng yếu.
Tí muốn biết xem trong khu vực của mình, gia đình nào điện sẽ yếu nhất?
Độ yếu của điện tại hộ gia đình X được tính bằng 0 nếu hộ đó là hộ phát điện, nếu hộ X có kết nối điện với hộ Y mà hộ Y ở gần máy phát hơn, độ yếu tại hộ X = độ yếu tại hộ Y + 1. Nếu hộ X không có điện thì có độ yếu bằng vô cùng (infinity).
Input
Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số hộ gia đình, M là số hộ gia đình có máy phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).
Dòng tiếp theo gồm M số là ID các hộ gia đình có máy phát điện (ID đánh số từ 0 tới N-1).
H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết hộ gia đình u có kết nối với hộ gia đình.
Output
In ra hộ gia đình có độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra hộ có ID nhỏ nhất.
Example
Test 1:
Input:
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
Output:
1
Test 2:
Input:
6 2 3
5 2
0 5
0 1
3 4
Output:
3
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-22 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2019-03-27 09:52:25
P145SUMH: https://e16cn-ptit.blogspot.com/2019/03/p145sumh-round-5h-he-thong-dien.html |
|
|
2016-07-13 12:59:14
test 2 ??? |
