結果

問題 No.1244 Black Segment
ユーザー LyricalMaestro
提出日時 2025-05-03 18:54:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 193 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 758 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 90,984 KB
最終ジャッジ日時 2025-05-03 18:54:22
合計ジャッジ時間 8,189 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1244

from collections import deque

MAX_VALUE = 10 ** 18

def main():
    N, M, A, B = map(int, input().split())
    A -= 1
    B -= 1
    lr = []
    for _ in range(M):
        l, r = map(int, input().split())
        lr.append((l - 1, r - 1))

    next_nodes = [[] for _ in range(N + 1)]
    for l , r in lr:
        next_nodes[l].append(r + 1)
        next_nodes[r + 1].append(l)

    dists = [MAX_VALUE] * (N + 1)
    queue = deque()
    for i in range(A + 1):
        dists[i] = 0
        queue.append(i)

    while len(queue) > 0:
        v = queue.popleft()
        for w in next_nodes[v]:
            if dists[w] == MAX_VALUE:
                dists[w] = dists[v] + 1
                queue.append(w)
    
    answer = MAX_VALUE
    for b in range(B + 1, N + 1):
        answer = min(answer, dists[b])

    if answer == MAX_VALUE:
        print(-1)
    else:
        print(answer)


    





                


if __name__ == "__main__":
    main()
0