結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 20:53:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 414 ms / 2,000 ms |
コード長 | 901 bytes |
コンパイル時間 | 378 ms |
コンパイル使用メモリ | 82,908 KB |
実行使用メモリ | 107,224 KB |
最終ジャッジ日時 | 2025-09-06 20:53:43 |
合計ジャッジ時間 | 9,954 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,M = map(int, input().split()) edge = [[] for i in range(N)] for i in range(M): u,v = map(int, input().split()) u-=1;v-=1 edge[u].append(v) edge[v].append(u) #print(edge) K = int(input()) if K > 0: A = list(map(int, input().split())) check = [0] * N for i in range(K): check[A[i]-1] = 1 dp = [[10**10]*5 for i in range(N)] from collections import deque que = deque([(0,0)]) dp[0][0] = 0 while que: dist,now = que.popleft() for _next in edge[now]: if check[_next] == 1: if dist+1 < 5: if dp[_next][dist+1] > dp[now][dist] + 1: dp[_next][dist+1] = dp[now][dist] + 1 que.append((dist+1,_next)) else: if dp[_next][0] > dp[now][dist] + 1: dp[_next][0] = dp[now][dist] + 1 que.append((0,_next)) print(dp[-1][0] if dp[-1][0] != 10**10 else -1)