結果
問題 | No.2431 Viral Hotel |
ユーザー |
![]() |
提出日時 | 2023-08-13 13:12:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 187 ms / 2,000 ms |
コード長 | 2,162 bytes |
コンパイル時間 | 1,924 ms |
コンパイル使用メモリ | 207,632 KB |
最終ジャッジ日時 | 2025-02-16 07:43:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INF = (1ll<<61)-1; int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); long long N,K,M,P; cin >> N >> K >> M >> P; vector<vector<long long>> G(N); for(int i=0;i<M;i++){ long long u,v; cin >> u >> v; u--;v--; G[u].push_back(v); G[v].push_back(u); } vector<long long> S(N),X(K); for(int i=0;i<N;i++){ cin >> S[i]; } for(int i=0;i<K;i++){ cin >> X[i]; X[i]--; } // {イベントが起こる日,イベントの種類,起こる頂点} priority_queue< array<long long,3>, vector<array<long long,3>>, greater<array<long long,3>> > que; long long Ans = 0; //回復したか vector<bool> recovered(N,false); //検疫が入ったか vector<bool> quarantined(N,false); //いま感染しているか vector<int> infected(N,false); //0: 回復 1: 隣に感染 2:検疫 for(int i=0;i<K;i++){ infected[X[i]] = true; que.push({P,0,X[i]}); que.push({S[X[i]],1,X[i]}); } while(!que.empty()){ array<long long,3> q = que.top(); que.pop(); //検疫が入った場合その後一切のアクションを起こさない if(quarantined[q[2]])continue; if(q[1] == 0){ //回復 infected[q[2]] = false; recovered[q[2]] = true; }else if(q[1] == 1){ //隣にうつす for(long long e:G[q[2]]){ if(recovered[e] || quarantined[e])continue; //すでにかかっていた場合検疫送り if(infected[e]){ que.push({q[0],2,e}); }else{ infected[e] = true; que.push({q[0]+P,0,e}); que.push({q[0]+S[e],1,e}); } } }else{ //検疫 Ans++; infected[q[2]] = false; quarantined[q[2]] = true; } } cout << Ans << endl; return 0; }