UOJ Logo Universal Online Judge

UOJ

#733. 【JOISC2022】复兴计划

附件下载 统计

JOI 镇是一个曾经辉煌的工业区。为了运输产品,其中建起了许多铁轨与火车站。尽管 JOI 镇已经衰落,那里仍有许多不再被使用的铁轨与火车站。

JOI 镇中有 $N$ 个火车站,编号为 $1,2,\dots,N$。其中还剩下 $M$ 条铁轨。第 $i$ 条铁轨 $(1\le i \le M)$ 双向连接火车站 $A_i$ 和 $B_i$,且其宽度为 $W_i$。保证能够从任意火车站经过若干条铁轨到达任意其他火车站。

你是 JOI 镇的镇长。你计划吸引铁路公司来使用 JOI 镇中留下的铁轨与火车站,使得 JOI 镇复苏成为「铁路之镇」。

于是,共有 $Q$ 个铁路公司申请参与这个复兴计划。然而,不同公司的火车所需的铁轨宽度也有所不同。这意味着你需要重建这些铁轨,使得它们都匹配对应公司的火车。

第 $j$ $(1\le j\le Q)$ 家铁路公司的火车所需的铁轨宽度为 $X_j$。为了迎合公司 $j$,要求满足以下条件:

条件:保证能够从任意火车站只经过宽度为 $X_j$ 的铁轨到达任意其他火车站。

为了满足上述条件,你可以按如下方式重建铁轨任意次:

重建:选择一条铁轨,你可以重建其使得其宽度增加或减少 $1$ 并花费 $1$。然而,若其宽度为 $1$,则不能再减少其宽度。

为了确定你能满足哪些公司,你需要求出迎合公司 $j$ 所需要的最小花费。

请写一个程序,对于给定的火车站、铁轨与铁路公司的信息,计算迎合公司 $j$ 所需要的最小花费。

输入格式

第一行,两个正整数 $N,M$,表示火车站的个数和铁轨的条数。

接下来 $M$ 行,其中第 $i$ $(1 \le i \le M)$ 行包含三个正整数 $A_i, B_i, W_i$,表示第 $i$ 条铁轨连接的火车站和其宽度。

第 $M+2$ 行,一个正整数 $Q$,表示铁路公司的个数。

接下来 $Q$ 行,其中第 $j$ $(1 \le j \le Q)$ 行包含一个正整数 $X_j$,表示第 $j$ 个铁路公司的火车需要的铁路宽度。

输出格式

输出 $Q$ 行,第 $j$ $(1\le j\le Q)$ 包含一个整数,表示迎合公司 $j$ 所需要的最小花费。

样例一

input

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

output

8
2
5
10
9
21

explanation

例如,为了迎合公司 $1$,若你按如下方式重建铁轨,将会花费 $8$。

  1. 将铁轨 $6$ 的宽度减少 $4$。
  2. 将铁轨 $9$ 的宽度减少 $3$。
  3. 将铁轨 $10$ 的宽度增加 $1$。

可以证明不可能用少于 $8$ 的花费迎合公司 $1$。因此,在第一行输出 $8$。

该样例满足子任务 $1,2,4,5,6$ 的限制。

样例二

input

3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4

output

1
1
2
0

explanation

该样例满足所有子任务的限制。

样例三

见附件下载中的 ex_reconstruction3.inex_reconstruction3.ans

该样例满足子任务 $2,4,5,6$ 的限制。

数据范围与提示

对于所有数据,满足:

  • $2 \le N \le 500$。
  • $N-1 \le M \le 100\,000$。
  • $1 \le Q \le 1\,000\,000$。
  • $1 \le A_i \lt B_i \le N$ $(1\le i\le M)$。
  • $1 \le W_i \le 10^9$ $(1\le i\le M)$。
  • $(A_i,B_i,W_i)\ne(A_j,B_j,W_j)$ $(1\le i\lt j\le M)$。
  • 保证能够从任意火车站经过若干条铁轨到达任意其他火车站。
  • $1 \le X_j \le 10^9$ $(1\le j\le Q)$。
  • $X_j \lt X_{j+1}$ $(1\le j\lt Q)$。

详细子任务附加限制及分值如下表所示:

子任务编号 附加限制 分值
$1$ $M \le 16$,$Q \le 10$ $3$
$2$ $Q\le 10$ $4$
$3$ $B_i = A_i+1$ $(1\le i\le M)$ $7$
$4$ $M\le 1\,000$ $28$
$5$ $Q\le 20\,000$ $35$
$6$ 无附加限制 $23$

时间限制:$\texttt{5s}$

空间限制:$\texttt{1GB}$