結果
問題 | No.2431 Viral Hotel |
ユーザー |
|
提出日時 | 2023-08-19 15:36:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 1,154 bytes |
コンパイル時間 | 2,567 ms |
コンパイル使用メモリ | 202,424 KB |
最終ジャッジ日時 | 2025-02-16 11:36:24 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,K,M,P;cin>>N>>K>>M>>P;vector<vector<int>>G(N);for(int i=0;i<M;i++){int A,B;cin>>A>>B;--A,--B;G[A].push_back(B);G[B].push_back(A);}vector<int>S(N);for(int &i:S)cin>>i;vector<int>dist(N,(int)1e9),v_cnt(N,0),owari(N,0);priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>pq;for(int i=0;i<K;i++){int T;cin>>T;--T;dist[T]=0;pq.push({0,0,T});}while(pq.size()){int v=pq.top()[2],d=pq.top()[0],t=pq.top()[1];pq.pop();if(owari[v])continue;if(t==0){if(d<dist[v]+P){v_cnt[v]+=1;}if(v_cnt[v]>=2){pq.push({d,2,v});}if(d>dist[v])continue;pq.push({d+S[v],1,v});}else if(t==1){for(int i:G[v]){if(dist[i]>d){dist[i]=d;}if(dist[i]+P>d){pq.push({d,0,i});}}}else if(t==2){owari[v]=1;}}int ans=accumulate(owari.begin(),owari.end(),0);cout<<ans<<'\n';}