結果
問題 |
No.1244 Black Segment
|
ユーザー |
![]() |
提出日時 | 2020-10-02 23:55:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,100 bytes |
コンパイル時間 | 1,995 ms |
コンパイル使用メモリ | 201,008 KB |
最終ジャッジ日時 | 2025-01-15 01:28:42 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;} template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;} #define all(x) (x).begin(),(x).end() #define debug(x) cerr << #x << " = " << (x) << endl; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,M,A,B; cin >> N >> M >> A >> B; A--,B--; vvec<int> g(N+1); for(int i=0;i<M;i++){ int l,r; cin >> l >> r; l--,r--; int f = max(A,l),t = min(B,r)+1; g[f].push_back(t); g[t].push_back(f); } int inf = 1e9; vec<int> dp(N+1,inf); dp[A] = 0; queue<int> Q; Q.push(A); while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto& to:g[cur]){ if(dp[to]==inf){ dp[to] = dp[cur]+1; Q.push(to); } } } cout << (dp[B+1]==inf? -1:dp[B+1]) << "\n"; }