学校
【问题描述】
众所周知,HXY家离学校很远。于是,HXY每天算准了时间出发,以保证能在上课铃响前10^-1000000秒到达学校。
不幸的是,CZ市最近正在修路。这就导致有些路可能无法通行,因而可能导致HXY迟到。
HXY不打算改变他的出发时间,现在他告诉你他通过每一条路的时间,他想要知道如果某条路被维修了,那么他是否能避免迟到?
【输入格式】
第一行输入两个正整数n,m,分别表示点数(路口)和边数(路)。
第二行输入两个正整数S,T,表示家标号为S,学校标号为T。
接下来m行,每行三个整数x,y,z,表示有一条连接x,y的道路,HXY走过该路所需的时间为z。
接下来一个整数Q,表示询问的个数。
最后Q行,每行一个正整数x,表示询问若第x条边正在维修,HXY是否能按时到校。
【输出格式】
输出Q行。
对于每一个询问,若HXY能准时到校输出一行一个字符串“Yes”,否则输出“No”。(字符串严格匹配,不含双引号)
Sample 1
【输入样例】
8 11
1 8
1 2 3
1 3 1
2 3 1
2 4 5
2 5 1
4 5 4
3 5 2
5 6 4
6 7 5
6 8 2
7 8 5
5
2
3
8
4
10
【输出样例】
No
Yes
No
Yes
No
Limitation
1s, 256MB for each test case.
对于30%的数据,Q,N≤100,M≤500;
对于100%的数据,1≤Q,N≤40000,M≤200000,保证源点到任意点的最短路长度不超过10^9。
信息
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 46
- 已通过
- 4
- 通过率
- 9%
- 上传者