Submission #25339435

---

Source Code Expand

#include "bits/stdc++.h"

#define int long long

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
const ll INF = (1LL << 61);
ll mod = 998244353;

int N, M, Q;
vector<P>G[100010];
int ans[200010];
int R[200010], wh[200010];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back({ b, i });
		G[b].push_back({ a, i });
	}
	for (int i = 0; i < M; i++)wh[i] = Q;
	for (int i = 0; i < Q; i++) {
		cin >> R[i]; R[i]--;
		wh[R[i]] = i;
	}
	ans[0] = Q;
	for (int i = 1; i < N; i++)ans[i] = -1;
	queue<int>q;
	vector<int>dist(N, INF);
	dist[0] = 0;
	q.push(0);
	while (!q.empty()) {
		int v = q.front(); q.pop();
		for (auto nv : G[v]) {
			if (dist[v] + 1 < dist[nv.first]) {
				dist[nv.first] = dist[v] + 1;
				q.push(nv.first);
			}
			if (dist[v] + 1 == dist[nv.first]) {
				ans[nv.first] = max(ans[nv.first], min(ans[v], wh[nv.second]));
			}
		}
	}
	vector<int>res(Q + 1);
	for (int i = 0; i < N; i++) {
		res[ans[i]]++;
	}
	for (int i = 0; i < Q; i++)res[i + 1] += res[i];
	for (int i = 0; i < Q; i++) {
		cout << res[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result