結果
問題 | No.1244 Black Segment |
ユーザー |
👑 ![]() |
提出日時 | 2020-10-02 22:25:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 777 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 90,288 KB |
最終ジャッジ日時 | 2024-07-17 21:53:04 |
合計ジャッジ時間 | 6,678 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
"""https://yukicoder.me/problems/no/1244ダイクストラ右に進む = 黒に塗る左に進む = 白で塗りなおすで解けるはず"""from sys import stdinimport sysfrom collections import dequeN,M,A,B = map(int,stdin.readline().split())lis = [ [] for i in range(10**5+10) ]for i in range(M):l,r = map(int,stdin.readline().split())lis[l].append(r+1)lis[r+1].append(l)d = [float("inf")] * (10**5+10)q = deque([])for i in range(A+1):if len(lis[i]) > 0:q.append(i)d[i] = 0while len(q):now = q.popleft()for nex in lis[now]:if d[nex] > d[now] + 1:d[nex] = d[now] + 1q.append(nex)ans = min(d[B+1:])if ans == float("inf"):print (-1)else:print (ans)