結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー hitori6541
提出日時 2025-09-06 14:10:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 388 ms / 2,000 ms
コード長 811 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 116,444 KB
最終ジャッジ日時 2025-09-06 14:10:32
合計ジャッジ時間 8,719 ms
ジャッジサーバーID
（参考情報） 		judge / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]
G = [[] for _ in range(N)]
for a, b in E:
    a, b = a-1, b-1
    G[a].append(b); G[b].append(a)
K = int(input())
if K:
    A = [int(x) - 1 for x in input().split()]
    A = set(A)
else:
    A = set()

inf = float("inf")
rank = [[inf]*N for _ in range(5)]
Q = deque([(0, 0)])
rank[0][0] = 0
while Q:
    state1, v1 = Q.popleft()
    r2 = 1 + rank[state1][v1]
    for v2 in G[v1]:
        if v2 in A:
            state2 = 1 + state1
        else:
            state2 = 0
        if state2 >= 5:
            continue
        if r2 < rank[state2][v2]:
            rank[state2][v2] = r2
            Q.append((state2, v2))

ans = min(rank[i][N-1] for i in range(5))
print(ans if ans < inf else -1)
0