結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:50:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 441 ms / 2,000 ms |
コード長 | 1,081 bytes |
コンパイル時間 | 422 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 109,172 KB |
最終ジャッジ日時 | 2025-09-06 13:51:06 |
合計ジャッジ時間 | 9,167 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from collections import deque, defaultdict, Counter from bisect import bisect_left, bisect_right from itertools import permutations, combinations from heapq import heappop, heappush import math, sys # input = sys.stdin.readline _int = lambda x: int(x)-1 MOD = 998244353 #10**9+7 INF = 1<<60 Yes, No = "Yes", "No" N, M = map(int, input().split()) E = defaultdict(list) for _ in range(M): u, v = map(_int, input().split()) E[u].append(v) E[v].append(u) iwai = [0]*N K = int(input()) if K > 0: A = list(map(int, input().split())) for i in range(K): iwai[A[i]-1] = 1 vis = [[INF]*5 for _ in range(N)] vis[0][0] = 0 q = deque([(0, 0)]) while q: i, k = q.popleft() if vis[i][k] == -1: continue for j in E[i]: if iwai[j]: if k == 4: continue if vis[j][k+1] != INF: continue vis[j][k+1] = vis[i][k]+1 q.append((j, k+1)) else: if vis[j][0] != INF: continue vis[j][0] = vis[i][k]+1 q.append((j, 0)) ans = min(vis[N-1]) if ans == INF: ans = -1 print(ans)