日期：2026年3月17日
ZeroJudge 題目連結：c125. 00534 - Frogger
解題想法
先讀取所有石頭的位置，計算任意兩個石頭之間的距離，存入二維陣列 $dist$ 之中，其中 $dist[i][j]$ 代表石頭 $i, j$ 之間的距離。 開一個陣列 $ans$，儲存到達第 $i$ 個石頭的路徑上單次跳躍距離最大值之中的最小值。接下來用一個最小優先佇列 $pq$，資料為 $(距離, 石頭索引值)$，代表到第 $i$ 顆石頭的路徑上最大的單次跳躍距離，距離最小的資料放上面。如果 $pq$ 還有資料，而且 $pq$ 最上面的石頭索引值不等於 $1$（終點），while 迴圈繼續執行。每次取出 $pq$ 最上方的資料，目前的距離 $curr$、石頭索引值 $u$，掃過石頭 $v ~(0 \leq v \leq n-1)$，取 $curr$ 與 $dist[u][v]$ 較大者為新的距離 $new_{dis}$，如果 $new_{dis} < ans[v]$，更新 $ans[v]$，並將 ${new_{dis}, v}$ 加入 $pq$。
Python 程式碼
使用時間約為 37 ms，記憶體約為 4.1 MB，通過測試。
import sys, heapq
def cal_dis(a, b): # 計算距離用的函式
return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5
ca = 0
result = []
for line in sys.stdin:
if not line.strip(): continue
n = int(line) # n 顆石頭
if n == 0: break # 中止迴圈的條件
ca += 1
if ca > 1: result.append("\n") # 從第 2 筆測資開始要先空一行
stones = [tuple(map(float, sys.stdin.readline().split())) for _ in range(n)] # 石頭位置
dist = [[0.0]*n for _ in range(n)] # 石頭之間的距離
for i in range(n):
for j in range(n):
if i == j: continue
d = cal_dis(stones[i], stones[j])
dist[i][j] = d
dist[j][i] = d
ans = [float('inf')]*n # 到達第 i 個石頭的路徑上單次跳躍距離最大值之中的最小值
pq = [(0.0, 0)] # (距離, 石頭索引值)，代表到第 $i$ 顆石頭的路徑上最大的單次跳躍距離
while pq and pq[0][1] != 1: # pq 還有資料，而且 pq 最上面的石頭索引值不等於 1
curr, u = heapq.heappop(pq) # 取出 pq 最上方的資料，目前的距離 curr、石頭索引值 u
for v in range(n): # 掃過石頭 v = 0 ~ n-1
if v == u: continue # 同一顆石頭，跳過
new_dis = max(curr, dist[u][v]) # 新的距離
if new_dis < ans[v]: # 新的最小值
ans[v] = new_dis # 更新 ans[v]
heapq.heappush(pq, (new_dis, v)) # (new_dis, v) 加入 pq
result.append(f"Scenario #{ca:d}\nFrog Distance = {ans[1]:.3f}\n")
sys.stdout.write("".join(result))
