In Froggy’s city, there are n intersections and m roads in a city. Each road connects two different intersections, and there is no more than one road between any pair of intersections. The mayor plans to build n towers to promote tourism. The heights of the towers are h1, h2, . . . , hn. The towers must be placed at the intersections of roads, and we can only place at most one tower on each intersection. If we place a tower of height h on an intersection of k roads, then we must build h steps of stairs for the entrance of each road. In total, we have to build kh steps of stairs for such case. Froggy is the contractor and he wants to minimize the cost of the construction of the stairs. He can decide the placement of the towers without violating the aforementioned constraints. He wonders how many steps of stairs are required to build the towers. Please write a program to compute the minimum number of steps of stairs.
The first line contains two integers n and m indicating that there are n intersections of roads and m roads in Froggy’s city. The i th of the following m lines contains two integers ui and vi indicating that there is a road between the u th i and the v th i intersections. The last line contains n integers h1, h2, . . . , hn indicating the heights of the towers.
Output the minimum number of steps of stairs to build the towers. Technical Specification
• 1 ≤ n ≤ 2 · 105
• 0 ≤ m ≤ 106
• 1 ≤ ui < vi ≤ n, for i in [1, m]
• ui ≠ uj or vi ≠ vj for i, j in [1, m] and i ≠ j
• 1 ≤ hi ≤ 106 , for i in [1, n]
3 2 1 3 2 3 4 4 1
10
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||