結果
問題 |
No.1244 Black Segment
|
ユーザー |
![]() |
提出日時 | 2021-02-12 20:04:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 797 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 97,408 KB |
最終ジャッジ日時 | 2024-07-19 18:55:29 |
合計ジャッジ時間 | 7,595 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
from collections import deque import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) inf = 10**9 N, M, A, B = map(int, input().split()) source = 0 sink = N + 2 G = [[] for _ in range(N + 3)] for _ in range(M): L, R = map(int, input().split()) R += 1 G[L].append((R, 1)) G[R].append((L, 1)) for i in range(1, A + 1): G[source].append((i, 0)) for i in range(B + 1, N + 2): G[i].append((sink, 0)) d = [inf] * (N + 3) d[source] = 0 q = deque([source]) while q: s = q.popleft() ds = d[s] for t, dt in G[s]: if d[t] >= inf: if dt == 0: d[t] = ds q.appendleft(t) else: d[t] = ds + dt q.append(t) ans = d[sink] if ans >= inf: ans = -1 print(ans)