結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:44:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 457 ms / 2,000 ms |
コード長 | 1,196 bytes |
コンパイル時間 | 230 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 113,416 KB |
最終ジャッジ日時 | 2025-09-06 13:45:02 |
合計ジャッジ時間 | 8,960 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
# 自作ライブラリ # https://github.com/takumi-okamoto/competitive-programming-public/tree/main/mylib import sys from collections import deque # sys.setrecursionlimit(10**8) def debug(*args): print(*args, file=sys.stderr) def main(): n, m = map(int, input().split()) edges = [[] for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 edges[u].append(v) edges[v].append(u) INF = 10**18 # INF = float("inf") dist = [[INF] * 5 for _ in range(n)] k = int(input()) if k > 0: a = set(map(lambda x: int(x) - 1, input().split())) else: a = set() que = deque([(0, 0, 0)]) # dist, pos, count while que: d, p, ct = que.popleft() if dist[p][ct] <= d: continue dist[p][ct] = d for q in edges[p]: if q in a: if ct < 4: que.append((d + 1, q, ct + 1)) else: que.append((d + 1, q, 0)) ans = min(dist[-1]) # for i in range(n): # debug(i + 1, dist[i]) print(ans if ans < INF else -1) if __name__ == "__main__": main()