编程题
### 问题描述 小齐在管理 $Air$ $Moo$,一家连接 $N$ 牧场的航空公司。这些牧场中有 $K$ 个被指定为航空枢纽。目前,$Air$ $Moo$ 提供了 $M$ 条单程航班,其中第 $i$ 条航班从牧场 $u_i$ 飞往牧场 $v_i$,费用为 $d_i$。每条航班至少有一个端点在航空枢纽上。同时,小齐收到了 $Q$ 条牛们度假的单程旅行请求,其中第 $i$ 条请求是从牧场 $a_i$ 到牧场 $b_i$。 请帮助小齐计算能够满足的旅行请求数量及其最小总费用。 ### 输入格式 第$1$行:四个整数 $N, M, K, Q$。 接下来的 $M$ 行:每行三个整数 $u_i, v_i, d_i$,表示一条航班。 接下来的 $K$ 行:每行一个整数,表示一个航空枢纽的编号。 接下来的 $Q$ 行:每行两个整数 $a_i, b_i$,表示一条旅行请求。 ### 输出格式 满足的旅行请求数量和满足的旅行请求的最小总费用。 ### 样例输入 ``` 3 3 1 2 1 2 10 2 3 10 2 1 5 2 1 3 3 1 ``` ### 样例输出 ``` 1 20 ``` ### 评测数据规模 $1 \leq N, M, K, Q \leq 20,000$。
查看答案
赣ICP备20007335号-2