結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:40:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 374 ms / 2,000 ms |
コード長 | 995 bytes |
コンパイル時間 | 450 ms |
コンパイル使用メモリ | 82,800 KB |
実行使用メモリ | 106,496 KB |
最終ジャッジ日時 | 2025-09-06 14:40:24 |
合計ジャッジ時間 | 8,631 ms |
ジャッジサーバーID (参考情報) |
judge / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from collections import deque N, M = map(int, input().split()) graph = [[] for _ in range(N)] for _ in range(M): u, v = map(lambda x: int(x) - 1, input().split()) graph[u].append(v) graph[v].append(u) K = int(input()) if K > 0: exist_yiwiy9 = set(map(lambda x: int(x) - 1, input().split())) else: exist_yiwiy9 = set() INF = 10**20 dist = [[INF] * N for _ in range(5)] dist[0][0] = 0 que = deque([(0, 0)]) while que: cur_yiwiy9, cur = que.popleft() for nxt in graph[cur]: nxt_yiwiy9 = cur_yiwiy9 if nxt in exist_yiwiy9: nxt_yiwiy9 += 1 if nxt_yiwiy9 >= 5: continue else: nxt_yiwiy9 = 0 if dist[nxt_yiwiy9][nxt] <= dist[cur_yiwiy9][cur] + 1: continue dist[nxt_yiwiy9][nxt] = dist[cur_yiwiy9][cur] + 1 que.append((nxt_yiwiy9, nxt)) # print(*dist, sep="\n") ans = min(dist[cnt_yiwiy9][N - 1] for cnt_yiwiy9 in range(5)) print(ans if ans < INF else -1)