結果
問題 | No.2431 Viral Hotel |
ユーザー |
![]() |
提出日時 | 2023-08-14 21:56:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 182 ms / 2,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 1,834 ms |
コンパイル使用メモリ | 205,336 KB |
最終ジャッジ日時 | 2025-02-16 08:09:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using pli = pair<ll,int>;int main(){int n, k, m, p; cin >> n >> k >> m >> p;vector<vector<int>> g(n);while (m--){int u, v; cin >> u >> v; u--, v--;g[u].emplace_back(v);g[v].emplace_back(u);}vector<ll> s(n);for (int i = 0; i < n; i++) cin >> s[i];/*0 : none1 : infected2 : cured3 : infected again*/vector<ll> status(n,0);priority_queue<pli,vector<pli>,greater<pli>> pque;auto id = [&](ll t, int type){return t * 3 + type;};while (k--){int x; cin >> x; x--;pque.push(pli(id(0,2),x));}int ans = 0;while (!pque.empty()){auto [tt, v] = pque.top(); pque.pop();ll t = tt / 3;int type = tt % 3;if (type == 0){if (status[v] == 3) continue;status[v] = 2;}if (type == 1){if (status[v] == 3) continue;for (int u : g[v]){pque.push(pli(id(t,2),u));}}if (type == 2){if (status[v] >= 2) continue;if (status[v] == 0){status[v] = 1;pque.push(pli(id(t+s[v],1),v));pque.push(pli(id(t+p,0),v));}else {ans++;status[v] = 3;}}}cout << ans << endl;}