多始点Dijkstra.
各警備員に対して,警備している頂点を求める. 警備するたびに体力が減っていくと考えると, 残り体力を保持しながら遷移する. ただし,このままではTLE.
頂点 \(v\) であって,\(v\) を複数の警備員が警備されているものを 任意に取る. このとき,\(v\) 以降の警備は,残り体力が一番多い警備員に任せたとしても, 答えは変わらない.
実装:
多始点Dijkstra
注意は, chmax が true のときだけ遷移(push)すること.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m,k;
cin >> n >> m >> k;
vvll to(n);
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
priority_queue<pll> que;
vll rem(n, -INFL);
auto push = [&](ll hp, ll v) -> void {
if(hp < 0) return;
if(chmax(rem[v], hp)){ // do not forget!!
que.push({hp, v});
}
};
rep(i,k){
ll p,h;
cin >> p >> h;
--p;
push(h, p);
}
while(que.size()){
auto [ch,cv] = que.top(); que.pop();
for(auto nv: to[cv]){
push(ch-1, nv);
}
}
vll ans;
rep(i,n){
if(rem[i] != -INFL) ans.push_back(i+1);
}
cout << ans.size() << endl;
coutv(ans);
return 0;
}