結果
問題 | No.2431 Viral Hotel |
ユーザー |
![]() |
提出日時 | 2023-08-11 19:50:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,315 bytes |
コンパイル時間 | 2,209 ms |
コンパイル使用メモリ | 204,524 KB |
最終ジャッジ日時 | 2025-02-16 00:51:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 4 WA * 38 |
ソースコード
//Solution to Viral Hotel problem by writer: BortiK #include<bits/stdc++.h> using namespace std; int main(){ int N, K, M, P; cin >> N >> K >> M >> P; vector<vector<int>> adj(N); for(int i = 0; i < M; i++){ int u,v; cin >> u >> v; u--;v--; adj[u].push_back(v); adj[v].push_back(u); } vector<int> s(N); for(int i = 0; i < N; i++){ cin >> s[i]; } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> todo; vector<int> infected(N, -1); for(int i = 0; i < K; i++){ int x; cin >> x; x--; todo.push(make_pair(s[x],x)); infected[x] = 0; } vector<bool> quar(N, false); int answer = 0; while(!todo.empty()){ pair<int,int> x = todo.top(); todo.pop(); if(quar[x.second]) continue; for(int u: adj[x.second]){ if(infected[u] == -1){ infected[u] = x.first; todo.push(make_pair(x.first+s[u], u)); } else { if(infected[u]+P > x.first){ if(!quar[u]){ answer++; quar[u] = true; } } } } } cout << answer; }