結果
問題 |
No.1244 Black Segment
|
ユーザー |
|
提出日時 | 2021-02-24 16:48:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 445 ms / 2,000 ms |
コード長 | 606 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 105,220 KB |
最終ジャッジ日時 | 2024-09-24 17:39:18 |
合計ジャッジ時間 | 9,504 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
n,m,a,b=map(int,input().split()) lr=[list(map(int,input().split())) for _ in range(m)] g=[[] for _ in range(n+2)] for l,r in lr: r+=1 g[l].append(r) g[r].append(l) from heapq import heappush,heappop inf=float('inf') seen=[inf]*(n+2) ans=inf todo=[] for v0 in range(a+1): for nv in g[v0]: if nv>a: if seen[nv]==inf: todo.append([1,nv]) seen[nv]=1 while todo: c,v=heappop(todo) if v>b: ans=min(ans,c) continue if seen[v]!=c:continue for nv in g[v]: if a<nv and seen[nv]>c+1: seen[nv]=c+1 heappush(todo,[c+1,nv]) print(-1 if ans==inf else ans)