#G1106. [GESP202503 八级] 上学

[GESP202503 八级] 上学

[GESP202503 八级] 上学

时间限制:1.0 s 内存限制:512.0 MB

题目描述

C 城可以视为由 nn 个结点与 mm 条边组成的无向图。这些结点依次以 1,2,…,n1,2,\dots,n 标号,边依次以 1,2,…,m1,2,\dots,m 标号。第 ii 条边(1≤i≤m1\le i\le m)连接编号为 uiu_i 与 viv_i 的结点,长度为 lil_i 米。

小 A 的学校坐落在 C 城中编号为 ss 的结点。小 A 的同学们共有 qq 位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。第 ii 位同学(1≤i≤q1\le i\le q)告诉小 A,他的家位于编号为 hih_i 的结点,并且他每秒能行走 11 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?

输入格式

第一行,四个正整数 n,m,s,qn,m,s,q,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。

接下来 mm 行,每行三个正整数 ui,vi,liu_i,v_i,l_i,表示 C 城中的一条无向边。

接下来 qq 行,每行一个正整数 hih_i,表示一位同学的情况。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

4
3
1

数据范围

测试点 数据范围 说明
1~2 q=1q=1 无
3~4 1≤n≤5001\le n\le 500,1≤m≤5001\le m\le 500
全部 1≤n≤2×1051\le n\le 2\times 10^5,1≤m≤2×1051\le m\le 2\times 10^5,1≤q≤2×1051\le q\le 2\times 10^5,1≤ui,vi,s,hi≤n1\le u_i,v_i,s,h_i\le n,1≤li≤1061\le l_i\le 10^6 保证给定的图联通