結果
問題 | No.2431 Viral Hotel |
ユーザー |
![]() |
提出日時 | 2023-08-19 00:21:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 1,669 bytes |
コンパイル時間 | 3,015 ms |
コンパイル使用メモリ | 96,144 KB |
最終ジャッジ日時 | 2025-02-16 11:10:08 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <algorithm>using namespace std;typedef pair<int,int> pii;vector<int> G[100010];int s[100010],c[100010];bool cure[100010],iru[100010];int main(){int i,n,k,m,p; cin >> n >> k >> m >> p;for(i=0;i<m;i++){int u,v; cin >> u >> v; u--; v--;G[u].push_back(v); G[v].push_back(u);}for(i=0;i<n;i++){cure[i] = false; iru[i] = true;}map<int,vector<pair<int,int>>> ms;for(i=0;i<n;i++) cin >> s[i];for(i=0;i<k;i++){int x; cin >> x; x--;ms[p].push_back({-1,x});ms[s[x]].push_back({1,x});c[x] = 1;}while(ms.size()){auto x = *ms.begin();ms.erase(x.first);vector<pair<int,int>> v = x.second;sort(v.begin(),v.end());vector<int> del;for(auto pp:v){if(pp.first==-1){cure[pp.second] = true;}else{if(!iru[pp.second]) continue;for(int u:G[pp.second]){if(!cure[u]){if(!c[u]){c[u] = 1;ms[x.first + p].push_back({-1,u});ms[x.first + s[u]].push_back({1,u});}else{del.push_back(u);}}}}}for(int u:del){iru[u] = false;}}int ans = 0;for(i=0;i<n;i++){if(!iru[i]) ans++;}cout << ans << "\n";// for(i=0;i<n;i++) cout << iru[i];// cout << endl;}