結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)