AI题库 · GESP-C++八级题库
题目分享 #20402
上学
时间限制:1 s,内存限制:512 MB
【问题描述】
C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1、2、……、n 标号,边依次以 1、2、……、m 标号。
第 i 条边(1<=i<=m)连接编号为 ui 与 vi 的结点,长度为 li 米。
小 A 的学校坐落在 C 城中编号为 s 的结点。小 A 的同学们共有 q 位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。
第 i 位同学(1<=i<=q )告诉小 A,他的家位于编号为 hi 的结点,并且他每秒能行走 1 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?
【输入描述】
第一行,四个正整数 n、m、s、q,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。
接下来 m 行,每行三个正整数 ui、vi、li,表示 C 城中的一条无向边。
接下来 q 行,每行一个正整数 hi,表示一位同学的情况。
【输出描述】
共 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<=ui、vi、hi<=n ,1<=li<=10^6 。
保证给定的图联通。
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。