Problem
有一个由 \(N\) 个点 \(M\) 边的简单无向图，顶点编号为 \(1\) 到 \(N\)，边的编号为 \(1\) 到 \(M\)。
第 $ i $ 条边连接着点 $ a_i $ 和 $ b_i $。
在一些点上有编号为 \(1\) 到 \(K\) 的 \(K\) 个守卫。
守卫 $ i $ 位于顶点 $ p_i $，保护范围为 $ h_i \(。（这里所有的\) p_i $都是相互不同的）
如果一个点 $ v $ 满足以下条件，则称为被保护的点。
- 至少存在一个守卫 $ i $，使得点 $ v $ 与点 $ p_i $ 之间的距离小于或等于 $ h_i $。
顶点 $ u $ 和顶点 $ v $ 之间的距离是连接顶点 $ u $ 和顶点 $ v $ 的路径上的最小边数。
输出所有被保护的顶点，顺序是从小到大。
Solution
因为 \(i\) 号守卫可以保护距离不超过 \(h_i\) 的点，所以考虑定义 \(f_i\) 为 \(i\) 点可以保护的距离。
初始化：
- 将 \(f\) 全赋为 \(-1\)；
- 把每个守卫的 \(f\) 值设为 \(h_i\)。
然后从 \(1\) 点开始 BFS，对于当前点 \(u\)，遍历 \(u\) 连的点 \(v\)。
然后用 f[u] - 1 更新 \(f_v\)，如果更新成功，就将 \(v\) 加入处理用来处理的优先队列 \(q\)。
\(q\) 要从大到小的顺序，因为每次更新都是把当前点 \(u\) 的 \(f\) 值减少，为了尽量让 \(f_u\) 更大以更新更多的点，应让 \(q\) 从大到小。
特殊的，如果当前点 \(u\) 的 \(f_u \le 0\) 时，\(u\) 就对答案没有贡献，所以直接 continue。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define int long long
#define pi pair<int,int>
#define mk make_pair
#define w first
#define v second
const int N = 2e5 + 5;
int n, m, k;
int vis[N], dis[N];
vector<int> g[N];
vector<int> ans;
priority_queue<pi> q;
signed main() {
cin >> n >> m >> k;
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(dis, -1, sizeof(dis));
while (k--) {
int u, w;
cin >> u >> w;
dis[u] = w;
q.push(mk(w, u));
}
while (!q.empty()) {
int v = q.top().v;
q.pop();
for (int i : g[v])
if (dis[i] < dis[v] - 1) {
dis[i] = dis[v] - 1;
q.push(mk(dis[i], i));
}
}
for (int i = 1; i <= n; ++i)
if (dis[i] >= 0) ans.push_back(i);
cout << ans.size() << '\n';
for (int i : ans) cout << i << ' ';
return 0;
}