题目描述

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. As with any other sensible airline, 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.

Bessie is in charge of running the ticketing services for Air Bovinia. Unfortunately, while she was away chewing on delicious hay for a few hours, Q one-way travel requests for the cows' holiday vacations were received (1 <= Q <= 50,000), where the ith request is from farm a_i to farm b_i.

As Bessie is overwhelmed with the task of processing these tickets, please help her compute whether each ticket request can be fullfilled, 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.

是n个点m条有向边，求两两之间的最短路，要求路径上必须经过编号1~k的至少一个点

输入格式

* 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 fullfilled.

* Line 2: The minimum total cost of fulling the possible ticket requests

题目大意

有N($1 \le N \le 2\times 10^4$)个农场，用1…N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1…K中的农场作为枢纽($1 \le K \le 200 \le N$)。

当前共有 $M$($1 \le M \le 2\times 10^4$)条单向航线连接这些农场，从农场 $u_i$ 到农场 $v_i$, 将花费 $d_i$ 美元。($1 \le d_i \le 10^4$).

航空公司最近收到 $Q$($1 \le Q \le 5\times 10^4$)个单向航行请求。第 $i$ 个航行请求是从农场 $a_i$ 到农场 $b_i$，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

请计算可行航行请求的数量，及完成所有可行请求的总费用

3 3 1 2 
1 2 10 
2 3 10 
2 1 5 
2 
1 3 
3 1 

1 
20 

提示

For the first flight, the only feasible route is 1->2->3, costing 20. There are no flights leaving farm 3, so the poor cows are stranded there.