結果
問題 | No.1244 Black Segment |
ユーザー |
![]() |
提出日時 | 2021-02-06 07:12:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 1,669 bytes |
コンパイル時間 | 1,899 ms |
コンパイル使用メモリ | 201,940 KB |
最終ジャッジ日時 | 2025-01-18 13:23:32 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)#define srep(i,s,t) for (int i = s; i < t; ++i)using namespace std;typedef long long int ll;typedef pair<int,int> P;#define yn {puts("Yes");}else{puts("No");}struct edge{ int to, cost; };const int INF = 1001001001;const int MAX_N = 200005;const int MAX_V = 200005;vector<edge> G[MAX_V];int d[MAX_V];void dijkstra(int s){// greater<P>を指定することでfirstが小さい順に取り出せるようにするpriority_queue<P, vector<P>, greater<P> > que;fill(d, d+MAX_V, INF);d[s] = 0;que.push(P(0, s));while(!que.empty()){P p = que.top();que.pop();int v = p.second;if(p.first > d[v]) continue;for(int i=0; i<G[v].size(); i++){edge e = G[v][i];if(d[e.to] > d[v] + e.cost){d[e.to] = d[v] + e.cost;que.push(P(d[e.to], e.to));}}}}int main() {int n, m, a, b;cin >> n >> m >> a >> b;srep(i,1,a+1){edge e;e.to = i;e.cost = 0;G[0].push_back(e);}srep(i,b+1,n+2){edge e;e.to = n+2;e.cost = 0;G[i].push_back(e);}rep(i,m){int from,to,cost;cin >> from >> to;cost = 1;edge e1, e2;e1.to = to+1; e1.cost = cost;e2.to = from; e2.cost = cost;G[from].push_back(e1);G[to+1].push_back(e2);}dijkstra(0);int ans = d[n+2];if(ans >= INF) ans = -1;cout << ans << endl;return 0;}