P3096 [USACO13DEC] Vacation Planning G

【问题描述】

有 $N$ 个点 ($1 \le N \le 20,000$)，其中有 $K$ 个已被指定为枢纽点（$1 \le K \le 200，K \le N$）。

有 $M$ 条单向边 ($1 \le M \le 20,000$)，其中第 $i$ 条边 从 $u_i$ 到 $v_i$，费用为 $d_i$ ($1 \le d_i \le 10,000$) 。没有重边。

有 $Q$ 个请求 ($1 \le Q \le 50,000$)，其中第 $i$ 个请求是从点 $a_i$ 到点 $b_i$ 是否存在至少经过一个枢纽点的路径，如果存在求出最小费用。

【输入格式】

第 1 行4个整数 $N、M、K 、Q$。

下来 $M$ 行，每行三个整数 $u_i、v_i、d_i$。($1 \le u_i, v_i \le N, u_i \ne v_i$)。

下来 $K$ 个数，表示枢纽点的编号（范围为 $1 \dots N$）。

下来 $Q$ 行，每行两个数字 $a_i$ 到 $b_i$ ,表示一个请求。($1 \le a_i, b_i \le N, a_i \ne b_i$)。

【输出格式】

第 1 行一个整数，可以满足的请求数量。

第 2 行一个整数，满足可能的请求的最低总成本

【输入#1】

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

【输出#1】

1 
20

【提示】

对于第一个航班，唯一可行的路线是 1->2->3，花费 20。没有航班离开农场 3，所以可怜的奶牛被困在那里。