Bird Migration Monitoring
Time limit3sMemory limit512 MB
Given a DAG where every vertex is reachable from 0 and reaches N-1, choose a vertex subset covering every source-to-sink path; cost is (count of chosen vertices) times the largest chosen price, with some vertices unmonitorable. Minimize the cost.
- Level
Medium7 of 10
- Topics
- Graph, Dynamic programming, Greedy, Topological sort
- Solved
- No attempts yet
Problem
Each year, the Wildlife Protection Agency (WPA) tracks the migration of birds to assess the health of the bird population. During the migration, birds stop at places they consider safe to rest and eat. There are only a limited number of such spots, and the WPA uses them to check the tags attached to the birds' legs. Birds can follow different routes, so the WPA may have to cover several places to be sure of counting all the birds. Counting a bird more than once is not a problem, since each bird has a unique tag.
The routes the birds follow can be seen as a directed graph in which the vertices correspond to the possible stops of birds, and an edge links node a to node b whenever a bird can fly from a to b without stopping. The routes follow the birds' journey, so this graph cannot contain a cycle.
The WPA now has to decide on a set of places to monitor. Every bird resting in a monitored place is accounted for, and the agency wants the monitored set to be such that every bird is counted at least once. The WPA can choose among different technologies to monitor places. Some technologies are cheap but have a short range and can monitor only small places, while others cost a bit more but cover larger places. Using two different technologies is not reasonable, since it would mean tagging the birds with two different tag systems. For each resting place r, the agency has determined the price P(r) of the cheapest technology needed to monitor it. A place r can always be monitored with any technology whose price p > P(r). Therefore, if the WPA wants to monitor a set E of places, it pays maxr∈E(P(r)) per resting place, for a total of maxr∈E(P(r)) × |E|, where |E| is the size of E. Finally, some places simply cannot be monitored, because of their size or terrain.
The WPA asks you to compute the minimum total price it has to pay to count each migrating bird at least once.
Input
The input consists of the following lines:
- The first line contains two space-separated integers N (the number of stops) and M (the number of links).
- On line i + 2, for 0 ≤ i < N, the integer P(i), the price of the cheapest technology to monitor place i. If a place cannot be monitored, the value is −1.
- Each of the M remaining lines contains two space-separated integers a and b (0 ≤ a, b < N, a ≠ b), meaning that a bird can fly from place a to place b. The same pair a, b never appears twice.
By convention, place 0 is the birds' summer home and place N − 1 is the birds' destination. It may be possible to monitor only place 0 or only place N − 1. The graph is guaranteed to be acyclic, every place is reachable from 0, and place N − 1 is reachable from every place.
Output
Output a single line with a single integer: the minimum total price required to monitor all the birds during their migration. If it is not possible to count all the birds, output −1.
Constraints
- 2 < N ≤ 2 000;
- 2 < M ≤ 2 000;
- For all 0 ≤ i < N, P(i) = −1 or 1 ≤ P(i) ≤ 109.