結果
問題 |
No.2897 2集合間距離
|
ユーザー |
|
提出日時 | 2025-05-09 06:04:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 686 ms / 3,500 ms |
コード長 | 686 bytes |
コンパイル時間 | 418 ms |
コンパイル使用メモリ | 81,932 KB |
実行使用メモリ | 162,492 KB |
最終ジャッジ日時 | 2025-05-09 06:05:09 |
合計ジャッジ時間 | 10,468 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
from collections import deque d=deque() n=int(input()) m=10**3+1 maze=[[] for _ in range(m)] nlst=[list(map(int,input().split())) for _ in range(n)] q=int(input()) qlst=[list(map(int,input().split())) for _ in range(q)] INF=float("INF") dist=[[INF]*m for _ in range(m)] for i,j in nlst: dist[i][j]=0 d.append((i,j)) # print("A",d) dy,dx=[0,1,0,-1],[1,0,-1,0] while d: y,x=d.popleft() for i in range(4): ny,nx=y+dy[i],x+dx[i] if not(0<=ny<m and 0<=nx<m):continue if dist[ny][nx]!=INF:continue dist[ny][nx]=dist[y][x]+1 d.append((ny,nx)) ans=INF for i,j in qlst: # print("A",i,j,dist[i][j]) ans=min(dist[i][j],ans) print(ans) # for i in range(3): # print(*dist[i][:3])