Problem F
Traffic
Input: standard input
Output: standard output
Time Limit: 4 seconds
Dhaka city is getting crowded and noisy day by
day. Certain roads always remain blocked in congestion. In order that people avoid
shortest routes, and hence the crowded roads, to reach destination, the city
authority has made a new plan. Each junction of the city is marked with a
positive integer (£20) denoting the busyness of the junction. Whenever
someone goes from one junction (the source junction) to another (the
destination junction), the city authority gets the amount (busyness of destination – busyness of
source)3 from the traveler.
The authority has appointed you to find out the minimum total amount that it earns when someone goes from a certain junction (the zero point) to several others.
Input
The first line of each test case contains n (the number of
junctions, 0 £ n £ 200) followed by n integers denoting
the busyness of the junctions numbered 1 to n in that order. The next
line contains r, the number of roads in the city. Each of the next r
lines (one for each road) contains two junction-numbers (source, destination)
that the corresponding road connects (all roads are unidirectional). The next
line contains the integer q, the number of queries. The next q lines each
contain a junction-number. Input is terminated by EOF.
Output
For each set of output, print the set # (1, 2, … ) followed by q lines, one for
each query, each containing the minimum total earning when one travels from
junction 1 (the zero point) to the corresponding junction. However, for the
queries that gives less than 3 units of minimum total earning, print a '?'.
Sample Input
5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
Sample Output
Set #1
3
4
(Problem-setter:
Mustaq Ahmed, University of Waterloo)