J13 例题-8 最短距离

题目描述

有 $N$ 个村庄，编号 $1$ 到 $N$。

村庄之间有 $M$ 条无向道路，第 $i$ 条道路连接村庄 $a_i$ 和村庄 $b_i$，长度是 $c_i$。

所有村庄都是连通的。

共有 $K$ 个村庄有商店，第 $j$ 个有商店的村庄编号是 $x_j$。

然后给出 $Q$ 个询问，第 $k$ 个询问给出一个村庄的编号 $y_k$，问该村庄距离最近的商店有多远？

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含三个整数 $a_i,b_i,c_i$，表示第 $i$ 条道路连接村庄 $a_i$ 和村庄 $b_i$，长度是 $c_i$。

再一行包含整数 $K$。

接下来 $K$ 行，每行包含一个整数 $x_j$，表示第 $j$ 个有商店的村庄编号是 $x_j$。

再一行包含整数 $Q$。

接下来 $Q$ 行，每行包含一个整数 $y_k$，表示询问编号为 $y_k$ 的村庄与其距离最近的商店之间的距离。

输出格式

对于每个询问，输出该询问的结果。

输入样例

7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7

输出样例

3
1
3
0
0
6
0

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据： $2 \le N \le 10^5$，$N-1\le M \le min(N(N-1)/2,10^6)$，$1 \le Q \le 10^5$，$1 \le K \le N$, $1\le c_i\le10000$。