結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:26:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 489 ms / 2,000 ms |
コード長 | 1,076 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 116,324 KB |
最終ジャッジ日時 | 2025-09-06 14:26:58 |
合計ジャッジ時間 | 9,682 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from collections import deque n, m = map(int, input().split()) edges = [[] for _ in range(n+1)] for _ in range(m): u, v = map(int, input().split()) edges[u].append(v) edges[v].append(u) k = int(input()) if k != 0: iwai = set(list(map(int, input().split()))) else: iwai = set() visited = [[-1 for _ in range(5)] for _ in range(n+1)] queue = deque([(1, 1 if 1 in iwai else 0)]) visited[1][1 if 1 in iwai else 0] = (0, 0) while queue: v, count = queue.popleft() if v == n: ans = [v] now_count = count while visited[v][now_count] != (0, 0): ans.append(visited[v][now_count][0]) v, now_count = visited[v][now_count] print(len(ans) - 1) break for u in edges[v]: if u in iwai: new_count = count + 1 else: new_count = 0 if new_count >= 5: continue if visited[u][new_count] == -1: visited[u][new_count] = (v, count) queue.append((u, new_count)) else: print(-1)