Air Bovinia operates flights connecting the N farms that the cows live on (1 <= N <= 20,000). As with any airline, K of these farms have been designated as hubs (1 <= K <= 200, K <= N).

Currently, Air Bovinia offers M one-way flights (1 <= M <= 20,000), where flight i travels from farm u_i to farm v_i and costs d_i (1 <= d_i <= 10,000) dollars. For each of these flights, at least one of u_i and v_i is a hub. There is at most one direct flight between two farms in any given direction, and no flight starts and ends at the same farm.

Q one-way travel requests were received (1 <= Q <= 50,000), where the ith request is from farm a_i to farm b_i. Please compute whether each ticket request can be fulfilled, and its minimum cost if it can be done.

To reduce the output size, you should only output the total number of ticket requests that are possible, and the minimum total cost for them. Note that this number might not fit into a 32-bit integer.

Line 1: The integers N, M, K, and Q.

Lines 2..M + 1: Line i+1 contains u_i, v_i, and d_i. (1 <= u_i, v_i <= N, u_i != v_i)

Lines M + 2..M + K + 1: Each of these lines contains the ID of a single hub (in the range 1..N).

Lines M + K + 2..M + K + Q + 1: Two numbers per line, indicating a request for a ticket from farm a_i to b_i. (1 <= a_i, b_i <= N, a_i != b_i)

Line 1: The number of ticket requests that can be fulfilled.

Line 2: The minimum total cost of fulfilling the possible ticket requests.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > December > Gold