結果
問題 | No.1244 Black Segment |
ユーザー |
![]() |
提出日時 | 2023-07-16 02:31:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 1,486 bytes |
コンパイル時間 | 2,978 ms |
コンパイル使用メモリ | 254,400 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-09-17 10:29:34 |
合計ジャッジ時間 | 6,514 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;int main(){int n,m,a,b;cin>>n>>m>>a>>b;vector<vector<int>> g(n+2);a--;b--;for(int i = 0;i<m;i++){int l,r;cin>>l>>r;l--;g[l].push_back(r);g[r].push_back(l);}int ans = 1e9;vector<int> vis(n+2,1e9);for(int i = 0;i<n;i++){if(vis[i]<=1e8) continue;deque<int> que;que.push_back(i);vector<int> use;vis[i] = 0;while(que.size()){int ni = que.front();que.pop_front();use.push_back(ni);for(auto&to:g[ni]){if(vis[to]<=vis[ni]+1) continue;vis[to] = vis[ni]+1;que.push_back(to);}}for(auto&j:use) vis[j] = 1e9;for(auto&j:use){if(j<=a) {que.push_back(j);vis[j] = 1;}}while(que.size()){int ni = que.front();que.pop_front();for(auto&to:g[ni]){if(vis[to]<=vis[ni]+1) continue;vis[to] = vis[ni] + 1;que.push_back(to);}}for(auto&j:use){if(j==n+1) continue;if(j<=b) continue;ans = min(ans,vis[j]-1);}for(auto&j:use) vis[j] = 0;}if(ans>=1e8) cout<<-1<<endl;else cout<<ans<<endl;}