计算无向图中多位同学家到学校的最短上学时间

时间限制

1.0 s

内存限制

512.0 MB

题目描述

C城可以视为由n个结点与m条边组成的无向图，结点依次编号为1,2,…,n，边依次编号为1,2,…,m。第i条边（1≤i≤m）连接编号为u_i与v_i的结点，长度为l_i米。 小A的学校坐落在C城中编号为s的结点，共有q位同学，每位同学每秒能行走1米。请计算每位同学从家h_i出发到达学校的最短时间（单位：秒）。

输入格式

1. 第一行：四个正整数n, m, s, q，分别表示C城的结点数、边数、学校所在结点编号、同学数量。
2. 接下来m行：每行三个正整数u_i, v_i, l_i，表示C城中的一条无向边。
3. 接下来q行：每行一个正整数h_i，表示一位同学的家所在结点编号。

   输出格式

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

   样例

   输入样例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

   数据范围

• 对于20%的测试点，保证q=1
• 对于另外20%的测试点，保证1≤n≤500，1≤m≤500
• 对于所有测试点： 1≤n≤2×10^5，1≤m≤2×10^5，1≤q≤2×10^5 1≤u_i, v_i, s, h_i≤n，1≤l_i≤10^6 保证给定的图连通。