結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:51:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 418 ms / 2,000 ms |
コード長 | 771 bytes |
コンパイル時間 | 344 ms |
コンパイル使用メモリ | 82,904 KB |
実行使用メモリ | 104,912 KB |
最終ジャッジ日時 | 2025-09-06 13:51:45 |
合計ジャッジ時間 | 8,716 ms |
ジャッジサーバーID (参考情報) |
judge / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from collections import deque import sys input = sys.stdin.readline N, M = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u-=1 v-=1 G[u].append(v) G[v].append(u) K = int(input()) if K>0: A = set(map(int, input().split())) else: A = set() deq = deque() deq.append((0, 0)) INF = 10**9 dp = [[INF for _ in range(5)] for _ in range(N)] dp[0][0] = 0 while deq: v, c = deq.popleft() for nv in G[v]: if nv+1 in A: nc = c+1 else: nc = 0 if nc==5: continue if dp[nv][nc]>dp[v][c]+1: dp[nv][nc] = dp[v][c]+1 deq.append((nv, nc)) ans = min(dp[N-1]) if ans==INF: print(-1) else: print(ans)