結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:39:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 429 ms / 2,000 ms |
コード長 | 973 bytes |
コンパイル時間 | 186 ms |
コンパイル使用メモリ | 82,604 KB |
実行使用メモリ | 106,756 KB |
最終ジャッジ日時 | 2025-09-06 13:40:18 |
合計ジャッジ時間 | 8,988 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,M=map(int,input().split()) g=[[] for i in range(N)] for i in range(M): U,V=map(int,input().split()) g[U-1].append(V-1) g[V-1].append(U-1) K=int(input()) A=[] if K!=0: A=list(map(int,input().split())) iwai=[False for i in range(N)] for i in A: iwai[i-1]=True visited=[[10**18 for j in range(5)] for i in range(N)] from collections import deque q=deque([]) if iwai[0]: q.append([0,1]) visited[0][1]=0 else: q.append([0,0]) visited[0][0]=0 while len(q)>0: z_=q.popleft() z=z_[0] num=z_[1] for k in g[z]: if iwai[k] and num<=3: if visited[k][num+1]!=10**18: continue q.append([k,num+1]) visited[k][num+1]=visited[z][num]+1 elif not iwai[k]: if visited[k][0]!=10**18: continue q.append([k,0]) visited[k][0]=visited[z][num]+1 if min(visited[N-1])==10**18: print(-1) else: print(min(visited[N-1]))