题目描述

$C$ 城可以视为由 $n$ 个结点与 $m$ 条边组成的⽆向图 。这些结点依次以 $1 , 2,……, n$ 标号 ，边依次以 $1 , 2,……, m$ 标号。 第 $i$ 条边（ $1 ≤ i ≤ m$）连接编号为 $u_i$ 与 $v_i$的结点 ，长度为 $l_i$ 米 。 小$A$ 的学校坐落在 $C$ 城中编号为 $S$ 的结点。小$A$ 的同学们共有 $Q$ 位 ，他们想在保证不迟到的前提下 ，每天尽可能晚地出门上学 。 但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 $A$ 。 第 $i$ 位同学（ $1 ≤ i ≤ Q$）告诉小 $A$ ，他的家位于编号为 $h_i$ 的结点 ，并且他每秒能行走 $1$ 米 。请你帮小 $A$ 计算 ，每位同学从家出发需要多少秒才能到达学校呢？

输入描述

第一行， 四个正整数 $n, m, S, q$ ，分别表示 $C$ 城的结点数与边数 ，学校所在的结点编号， 以及小$A$ 同学们的数量。 接下来 $m$ 行 ，每行三个正整数 $u_i, v_i, l_i$，表⽰ C 城中的一条无向边。 接下来 $Q$ 行 ，每行一个正整数 $h_i$，表示一位同学的情况。

输出描述

共 $Q$ 行 ，对于每位同学 ，输出一个整数 ，表示从家出发到学校的最短时间。

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

4
3
1

提示/说明

【数据范围】 对于 $20\%$ 的测试点 ，保证 $Q = 1$ 。 对于另外 $20\%$ 的测试点 ，保证 $1 ≤ n ≤ 500 ，1 ≤ m ≤ 500$。 对于所有测试点 ，保证 $1 ≤ n ≤ 2 \times 10^5$， $1 ≤ m ≤ 2 \times 10^5$ ， $1 ≤ Q ≤ 2 \times 10^5$ ， $1 ≤ u_i, v_i, S_i, h_i ≤ n$， $1 ≤ l_i ≤ 10^6$ 。 保证给定的图联通。

来源

GESP_八级_2503