結果
問題 | No.2431 Viral Hotel |
ユーザー |
![]() |
提出日時 | 2023-09-01 21:29:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 1,590 bytes |
コンパイル時間 | 856 ms |
コンパイル使用メモリ | 76,756 KB |
実行使用メモリ | 11,004 KB |
最終ジャッジ日時 | 2025-01-03 07:25:00 |
合計ジャッジ時間 | 6,649 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include<iostream>#include<vector>#include<queue>using namespace std;int main( void ){int N, K, M, P;cin >> N >> K >> M >> P;vector<vector<int>> Graph( N );int u, v;for( int i = 0; i < M; i++ ){cin >> u >> v;u--, v--;Graph[u].push_back( v );Graph[v].push_back( u );}vector<int> S( N );for( int i = 0; i < N; i++ ){cin >> S[i];}vector<int> invasion_day( N, -1 ), qua_day( N, -1 );vector<int> status( N, 0 );priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;int x;for( int i = 0; i < K; i++ ){cin >> x, x--;q.push( make_pair( S[x], x ) );invasion_day[x] = 0;status[x] = 1;}pair<int, int> cur;int ans = 0;while( !q.empty() ){cur = q.top(), q.pop();if( status[cur.second] == 2 && qua_day[cur.second] != cur.first ) continue;for( int next : Graph[cur.second] ){if( status[next] == 2 ) continue;if( status[next] == 0 ){q.push( make_pair( cur.first + S[next], next ) );invasion_day[next] = cur.first;status[next] = 1;}else{if( invasion_day[next] + P > cur.first ){ans++;status[next] = 2;qua_day[next] = cur.first;}}}}cout << ans << endl;return 0;}