ZOJ Problem Set - 4001
BaoBao loves traveling very much. There are \(N\) cities marked on his traveling map, and some of them have food supplies while others have not.
During his journey, he must take enough food so that he won't starve. There are \(M\) roads on the map, each connecting two cities. These roads are bi-directional. For each road, we know the exact cost of food. Notice that only when BaoBao arrives in a city which is able to provide food can he refill his food to the maximum capacity.
BaoBao has \(Q\) journey plans. For each plan, it is guaranteed that both the starting city and the destination city have food supplies. Now BaoBao wants you to help him determine the maximum food capacity of his carriage for each plan. For his convenience, he hopes it can be as small as possible.
There is only one test case.
The first line of the input contains two integers \(N\) and \(M\) (\(1 \le N \le 10^5\), \(1 \le M \le 2 \times 10^5\)), denoting that there are \(N\) cities and \(M\) bi-directional roads.
The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\). If \(a_i = 1\), the \(i\)-th city has food supplies; If \(a_i = 0\), the \(i\)-th city has no food supplies.
The following \(M\) lines each contains three integers \(X\), \(Y\) and \(W\) (\(X \ne Y\), \(1 \le W \le 10^9\)), denoting that there is a road connecting the \(X\)-th and the \(Y\)-th city with a food cost of \(W\). It is guaranteed that there exists at most one road between each pair of \(X\) and \(Y\).
The following line contains an integer \(Q\) (\(1 \le Q \le 10^5\)), the number of queries.
The following \(Q\) lines each contains two integers \(X\) and \(Y\), denoting the starting city and the destination city for each query. It is guaranteed that both \(X\) and \(Y\) are cities with food supplies.
For each query output one line containing one integer, indicating the smallest food capacity.
6 7 1 0 1 0 1 1 1 2 2 1 4 1 2 3 2 4 5 4 3 6 10 3 5 2 5 6 5 2 1 6 1 5
Author: CHEN, Jingbang
Source: ZOJ Monthly, January 2018