bfs dijkstra 8个WA 12个MLE
查看原帖
bfs dijkstra 8个WA 12个MLE
1097884
shuhao楼主2024/8/2 10:34

样例过了

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10, M = 1e9+10, inf = 0x3f3f3f3f;
int n, m, q, u, v, a, l;
vector <int> g[N];
queue <int> que; int d[N];
void Dijkstra(int x, int y) {
	memset(d, inf, sizeof(d));
	while(!que.empty()) que.pop();
	d[x] = y; que.push(x);
	while(!que.empty()) {
		int k = que.front(); que.pop();
		if(d[k] == 0) continue;
		for(int w : g[k]) {
			d[w] = min(d[w], d[k] - 1);
			que.push(w);
		}
	}
}

int main() {
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	while(q--) {
		cin >> a >> l;
		Dijkstra(a, l);
		cout << "         ";
		if(d[1] == 0) cout << "Yes\n";
		else cout << "No\n";
	}
	
    return 0;
}

为啥有MLE

2024/8/2 10:34
加载中...