#G1106. [GESP202503 八级] 上学
[GESP202503 八级] 上学
[GESP202503 八级] 上学
时间限制:1.0 s 内存限制:512.0 MB
题目描述
C 城可以视为由 个结点与 条边组成的无向图。这些结点依次以 标号,边依次以 标号。第 条边()连接编号为 与 的结点,长度为 米。
小 A 的学校坐落在 C 城中编号为 的结点。小 A 的同学们共有 位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。第 位同学()告诉小 A,他的家位于编号为 的结点,并且他每秒能行走 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?
输入格式
第一行,四个正整数 ,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。
接下来 行,每行三个正整数 ,表示 C 城中的一条无向边。
接下来 行,每行一个正整数 ,表示一位同学的情况。
输出格式
共 行,对于每位同学,输出一个整数,表示从家出发到学校的最短时间。
样例 #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 | 无 | |
| 3~4 | , | |
| 全部 | ,,,, | 保证给定的图联通 |