P3096 [USACO13DEC] Vacation Planning G

题目描述 Air Bovinia 航空公司运营连接奶牛们居住的 $N$ 个农场的农场（$1 \le N \le 20,000$）。与任何航空公司一样，其中有 $K$ 个农场被指定为枢纽（$1 \le K \le 200$，$K \le N$）。 目前，Air Bovinia 提供 $M$ 条单向航班（$1 \le M \le 20,000$），其中第 $i$ 个航班从农场 $u_i$ 飞往农场 $v_i$，费用为 $d_i$ 美元（$1 \le d_i \le 10,000$）。与其他任何明智的航空公司一样，对于这些航班中的每一个，$u_i$ 和 $v_i$ 中至少有一个是枢纽。在任何给定的方向上，两个农场之间最多有一条直飞航班，并且没有航班从同一个农场起飞并降落在同一个农场。 Bessie 负责管理 Air Bovinia 的票务服务。不幸的是，当她离开几个小时去咀嚼美味的干草时，收到了 $Q$ 个奶牛假期度假的单向旅行请求（$1 \le Q \le 50,000$），其中第 $i$ 个请求是从农场 $a_i$ 到农场 $b_i$。 由于 Bessie 在处理这些票务时不知所措，请帮助她计算每个票务请求是否可以实现，以及如果可以的话，其最小费用是多少。 为了减少输出大小，你只需要输出可以实现的票务请求的总数，以及它们的最小总费用。请注意，这个数字可能无法放入 32 位整数中。

* 第 1 行：整数 $N$，$M$，$K$ 和 $Q$。 * 第 2 行到第 $M + 1$ 行：第 $i + 1$ 行包含 $u_i$，$v_i$ 和 $d_i$。（$1 \le u_i, v_i \le N$，$u_i \neq v_i$） * 第 $M + 2$ 行到第 $M + K + 1$ 行：每行包含单个枢纽的 ID（范围在 $1$ 到 $N$ 之间）。 * 第 $M + K + 2$ 行到第 $M + K + Q + 1$ 行：每行两个数字，表示从农场 $a_i$ 到 $b_i$ 的票务请求。（$1 \le a_i, b_i \le N$，$a_i \neq b_i$）

* 第 1 行：可以实现票务请求的数量。 * 第 2 行：实现所有可行票务请求的最小总费用。

对于第一个航班，唯一可行的路线是 $1 \to 2 \to 3$，花费 $20$ 美元。没有从农场 $3$ 起飞的航班，所以可怜的奶牛们被困在那里了。