Submission #42141197

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,m,k;
vector<int>graph[200005];
int dist[200005];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>m>>k;
	for(int i=1; i<=m; i++){
		int a,b; cin>>a>>b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
	}
	memset(dist,-1,sizeof(dist));
	priority_queue<pi,vector<pi>,less<pi>>pq;
	for(int i=1; i<=k; i++){
		int p,h; cin>>p>>h;
		dist[p] = h;
		pq.push({h,p});
	}
	while(!pq.empty()){
		int d = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if(d < dist[cur]) continue;
		if(!d) continue;
		for(int nxt : graph[cur]){
			if(dist[nxt] == -1 || dist[nxt] < d - 1){
				dist[nxt] = d - 1;
				pq.push({d-1,nxt});
			}
		}
	}
	vector<int>ans;
	for(int i=1; i<=n; i++) if(dist[i] != -1) ans.emplace_back(i);
	cout<<ans.size()<<'\n';
	for(int x : ans) cout<<x<<" ";
}

Submission Info

Judge Result