21.11.16模拟 学校

题意就是求出去掉一条边，还能按照原来的最短路的耗时从s到t

先一遍Dij求出s~t的最短路，然后从t bfs倒推回去，建立出最短路图C，然后在C上求割边
去掉的边若是C上的割边，那么就不能到达，否则能到达

const int N = 4e4 + 79;
const int M = 2e5 + 79;
struct graph {
	int head[N], tot = 1, next[M << 1], ver[M << 1], edge[M << 1], num[M << 1];
	inline void add(int id, int a, int b, int c) {
		ver[++tot] = b;
		num[tot] = id;
		next[tot] = head[a];
		head[a] = tot;
		edge[tot] = c;
	}
} G, C;
int n, m, s, t;
int d[N];
bool vis[N];
#define pii std::pair
std::priority_queue, std::greater >Q;
inline void Dijkstra() {
	memset(d, 0x3f, sizeof d);
	d[s] = 0;
	Q.push({0, s});
	while(Q.size()) {
		int x(Q.top().second);
		Q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		repg(x) {
			int y(G.ver[i]), z(G.edge[i]);
			if(d[y] > d[x] + z) {
				d[y] = d[x] + z;
				Q.push({d[y], y});
			}
		}
	}
}
int low[N], dfn[N], tim;
bool bridge[M << 1];
inline void tarjan(int x, int in_edge) {
	low[x] = dfn[x] = ++tim;
	repc(x) {
		int y(C.ver[i]);
		if(!dfn[y]) {
			tarjan(y, i);
			low[x] = min(low[x], low[y]);

			if(low[y] > dfn[x]) {
				bridge[C.num[i]] = 1;
			}
		} else if(C.num[i] != C.num[in_edge]) {
			low[x] = min(low[x], dfn[y]);
		}
	}
}


int q[N];
inline void init() {
	memset(vis, 0, sizeof vis);
	vis[t] = 1;
	q[++q[0]] = t;
	rep(_, 1, q[0]) {
		int x(q[_]);
		repg(x) {
			int y(G.ver[i]), z(G.edge[i]);
			if(d[y]+z == d[x] ) {

				C.add(G.num[i], x, y, z);
				C.add(G.num[i], y, x, z);
				if(!vis[y]) {
					vis[y] = 1;
					q[++q[0]] = y;
				}
			}
		}
	}
	tarjan(s, -1);
}

int main() {
	freopen("school.in","r",stdin);
	freopen("school.out","w",stdout);
	read(n);
	read(m);
	read(s);
	read(t);
	int a, b, c;
	rep(i, 1, m) {
		read(a);
		read(b);
		read(c);
		G.add(i, a, b, c);
		G.add(i, b, a, c);
	}
	Dijkstra();
	init();
	int Q, x;
	read(Q);
	while(Q--) {
		read(x);
		puts(bridge[x] ? "No" : "Yes");
	}
	return 0;
}