結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:05:57 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 952 ms / 2,000 ms |
コード長 | 924 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 12,160 KB |
実行使用メモリ | 45,012 KB |
最終ジャッジ日時 | 2025-09-06 14:06:16 |
合計ジャッジ時間 | 17,510 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
def ip():return int(input()) def mp():return map(int, input().split()) def lmp():return list(map(int, input().split())) # 岩プロコン2 E No.3263 違法な散歩道 from collections import deque N, M = mp() edge = [[] for _ in range(N)] for _ in range(M): u, v = map(lambda x:int(x)-1, input().split()) edge[u].append(v) edge[v].append(u) K = ip() A = list(map(lambda x:int(x)-1, input().split())) if K > 0 else [] I = [False] * N for a in A: I[a] = True que = deque() que.append((0, 0)) INF = 10**6 dist = [[INF] * 5 for _ in range(N)] dist[0][0] = 0 while que: v, c = que.popleft() for to in edge[v]: if I[to]: if c == 4: continue if dist[to][c+1] == INF: dist[to][c+1] = dist[v][c] + 1 que.append((to, c+1)) else: if dist[to][0] == INF: dist[to][0] = dist[v][c] + 1 que.append((to, 0)) ans = min(dist[N-1]) print(-1 if ans == INF else ans)