123Code...

Nội dung Bài tập

Mã:: ATM

Tên:: The Great ATM Robbery (APIO 2009)

Dạng thi:: oi

Thang điểm:: 10 điểm

Giới hạn thời gian:: 3 giây

Giới hạn bộ nhớ:: 256 MB

Được tạo bởi:: phuc

: Share

Input	Output
6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6	47

Input	Output
6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6	47

English Tiếng Việt The city of Siruseri has only one way roads. Roads meet at intersections and at every intersection, mandated by law, there is an ATM of the Bank of Siruseri. Strangely, the pubs in Siruseri are also located only at intersections, though not every intersection hosts a pub. Banditji plans to carry out the largest ATM robbery in the history of Siruseri. He will start from the city centre and drive around, robbing all the ATMs that he passes by, before ending the day at one of the city's pubs to celebrate his achievement. Using his well-honed hacking skills, Banditji has precise information about the amount of cash available at every ATM. He would like you to help him determine the total amount that he can rob by starting at the city centre and ending at one of the city's pubs. He can go through the same intersection or road any number of times. owever, there is no money to be picked up at an ATM after the rst visit. For instance, suppose the city had 6 intersections connected by roads as indicated below: The city centre is at intersection 1, marked by an incoming!, and the in-tersections where pubs are found are marked by a double circle. The amount of cash available at the respective ATMs is written above each intersection. In this case, Banditji can rob a total of 47 by following the route 1-2-4-1-2-3-5. Input format The rst line of input contains 2 integers N and M, where N is the number of intersections and M is the number of roads. This is following by M lines, each with two integers in the range 1; 2; : : : ;N, giving the starting and ending intersection for one of the roads. This is followed by N lines, each containing a single integer, giving the amount of cash available at the ATMs at the N intersections. The following line contains two integers S and P, where S is the starting intersection (the city centre) and P is the number of pubs. This is followed by a line with P integers listing the intersections that contain pubs. Output format The output should be a single integer, the maximum amount of money that Banditji can rob on his way from the city centre to any one of the pubs. Test Data In 50% of the inputs, N;M 3000. In all inputs, N;M 500000. The amount of cash available at a single ATM is always non-negative and never exceeds 4000. You are guaranteed that at least one pub can be reached from the city centre by following Siruseri's one way roads. Sample: Input Output 6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6 47 Thành phố Siruseri có một mạng lưới giao thông dày đặc, gồm N giao điểm và M con đường một chiều. Mỗi giao điểm được đặt một máy rút tiền tự động (ATM), hiện mỗi máy đang có số tiền Mi. Ngoài ra, một vài giao điểm có các quán bar (sẽ giải thích sau). Banditji đang dự tính một vụ trộm ngân hàng. Hắn sẽ xuất phát ở giao điểm S, đi qua một số giao điểm theo mạng lưới giao thông trong thành phố, “viếng thăm” và rút hết tiền ở các máy ATM hắn đi qua. Hắn sẽ kết thúc cuộc chơi tại một trong các quán bar trước khi biến mất. Hắn có thể đi qua một giao điểm nhiều lần, nhưng dĩ nhiên, hắn chỉ có thể rút tiền tại lần đầu tiên “viếng thăm” máy ATM tại giao điểm đó. Xác định số tiền tối đa mà Banditji có thể ăn trộm được. Dữ liệu đảm bảo hắn luôn có cách tẩu thoát về ít nhất một trong các quán bar. Input • Dòng đầu tiên chứa hai số nguyên dương N và M (1 ≤ N, M ≤ 5.10⁵). • M dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y chỉ ra một con đường một chiều từ x đến y (1 ≤ x, y ≤ N). • N dòng tiếp theo, mỗi dòng chứa một số nguyên Mi (0 ≤ Mi ≤ 4000) là số tiền hiện có trong máy ATM tại giao điểm i. • Dòng tiếp theo chứa hai số nguyên S và P lần lượt giao điểm mà Bandiji xuất phát và số lượng quán bar. • Trong 50% số test, 1 ≤ N, M ≤ 3000. Output • In ra số tiền tối đa Banditji có thể ăn trộm được. Ví dụ: Input Output 6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6 47 Mô tả test ví dụ. Banditji xuất phát tại thành phô 1. Hắn sẽ đi theo tuyến đường 1 ⇨ 2 ⇨ 4 ⇨ 1 ⇨ 2 ⇨ 3 ⇨ 5 và lấy được tiền tại tất cả các giao điểm trừ giao điểm 6. Tổng số tiền là 47.
Quảng cáo