U408062 学校
题目描述
众所周知,HXY 家离学校很远。于是,HXY 每天算准了时间出发,以保证能在上课铃响前 $10^{-10000000}$ 秒到达学校。
不幸的是,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`。(字符串严格匹配,不含双引号)
说明/提示
对于 $30\%$ 的数据,$Q, N \le 100, M \le 500$。
对于 $100\%$ 的数据,$1 \le Q, N \le 40000, M \le 200000$,保证源点到任意点的最短路长度不超过 $10^9$。
不保证没有重边。
不保证不卡某种已似的算法。