P3094 [USACO13DEC] Vacation Planning S

有N(1

* 第 1 行：四个整数 $N, M, K, Q$。 * 第 $2 \dots 1+M$ 行：第 $i+1$ 行包含航线 $i$ 的三个参数 $u_i, v_i, d_i$，分别对应航线的起点、终点和通行费用。 * 第 $2+M \dots 1+M+Q$ 行：第 $1+M+i$ 行包含第 $i$ 次航行请求的两个参数 $a_i, b_i$，分别对应航行的起点和终点。

* 第 1 行：$Q$ 个请求中，存在合法航行路径的请求总数量。 * 第 2 行：所有合法请求对应的最小航行费用的总和。

样例中共有3个农场，农场1是唯一的枢纽。存在三条航线：从农场3到农场1费用10，从农场1到农场3费用10，从农场1到农场2费用7。三个航行请求分别是3→2、2→3、1→2： - 3→2的合法路径为3→1→2，总费用10+7=17 - 2→3不存在合法路径，没有从农场2出发的航线 - 1→2本身起点就是枢纽，直接通行费用为7 最终统计得到2个合法请求，总费用17+7=24。