結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:20:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 451 ms / 2,000 ms |
コード長 | 820 bytes |
コンパイル時間 | 199 ms |
コンパイル使用メモリ | 82,664 KB |
実行使用メモリ | 112,768 KB |
最終ジャッジ日時 | 2025-09-06 13:21:06 |
合計ジャッジ時間 | 8,980 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from collections import deque N, M = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u, v = u-1, v-1 G[u].append(v) G[v].append(u) K = int(input()) if K: A = list(map(int, input().split())) else: A = [] INF = 1<<60 S = set() for a in A: S.add(a-1) visited = [[-1]*5 for _ in range(N)] visited[0][0] = 0 que = deque() que.append((0, 0)) while que: n, c = que.popleft() for v in G[n]: nc = c+1 if v not in S: nc = 0 if nc == 5: continue if visited[v][nc] == -1: visited[v][nc] = visited[n][c]+1 que.append((v, nc)) ans = INF for i in range(5): if visited[-1][i] != -1: ans = min(ans, visited[-1][i]) print(ans if ans != INF else -1)