結果

問題 No.2431 Viral Hotel
ユーザー kotatsugamekotatsugame
提出日時 2023-08-18 21:33:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 2,000 ms
コード長 1,100 bytes
コンパイル時間 952 ms
コンパイル使用メモリ 80,832 KB
実行使用メモリ 11,188 KB
最終ジャッジ日時 2024-11-28 05:53:46
合計ジャッジ時間 4,561 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cassert>
//#include<atcoder/modint>
using namespace std;
//using mint=atcoder::modint998244353;
int N,K,M,P;
vector<int>G[1<<17];
int S[1<<17];
int inf[1<<17];
bool ban[1<<17];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N>>K>>M>>P;
for(int i=0;i<M;i++)
{
int u,v;cin>>u>>v;
u--,v--;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=0;i<N;i++)
{
cin>>S[i];
inf[i]=-1;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
for(int i=0;i<K;i++)
{
int x;cin>>x;x--;
inf[x]=0;
Q.push(make_pair(inf[x]+S[x],x));
}
int bc=0;
vector<int>B;
while(!Q.empty())
{
int d=Q.top().first;
B.clear();
while(!Q.empty()&&Q.top().first==d)
{
int x=Q.top().second;
Q.pop();
if(ban[x])continue;
for(int v:G[x])
{
if(inf[v]==-1)
{
inf[v]=d;
Q.push(make_pair(inf[v]+S[v],v));
}
else if(inf[v]+P>d&&!ban[v])B.push_back(v);
}
}
for(int v:B)
{
bc+=!ban[v];
ban[v]=true;
}
}
cout<<bc<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0