結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:46:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 368 ms / 2,000 ms |
コード長 | 1,474 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 116,264 KB |
最終ジャッジ日時 | 2025-09-06 14:46:50 |
合計ジャッジ時間 | 7,596 ms |
ジャッジサーバーID (参考情報) |
judge / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from collections import deque import sys import os IS_LOCAL = os.environ.get("LOCAL") == "true" def debug(*args, sep=" ", end="\n", flush=False) -> None: if IS_LOCAL: print(*args, sep=sep, end=end, file=sys.stderr, flush=flush) def yn(flg: bool) -> bool: print('Yes' if flg else 'No') return flg def gcd(a, b): a = abs(a); b = abs(b) if a < b: a, b = b, a while b > 0: a, b = b, a % b return a def lcm(a, b): return a * b // gcd(a, b) def main(): readline = sys.stdin.readline N, M = map(int, readline().split()) L = 5 G = [[] for _ in range(N)] for _ in range(M): u, v = map(lambda x: int(x) - 1, readline().split()) G[u].append(v) G[v].append(u) int(input()) A = list(map(lambda x: int(x) - 1, readline().split())) Y = [False] * N for a in A: Y[a] = True def encode(l, i): return l * N + i q = deque() seen = set() q.append((0, 0, 0)) seen.add(0) while q: d, l, i = q.popleft() if i == N - 1: print(d) return for j in G[i]: if Y[j]: ll = l + 1 else: ll = 0 if ll >= L: continue xx = encode(ll, j) if xx in seen: continue seen.add(xx) q.append((d + 1, ll, j)) print(-1) if __name__ == "__main__": main()