ZeroJudge 解題筆記：c125. 00534 - Frogger

作者：王一哲
日期：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))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 500 kB，通過測試。

#include <cstdio>
#include <vector>
#include <cmath>
#include <utility>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

int main() {
    int n, ca = 0;
    while(scanf("%d", &n) != EOF && n != 0) {
        ca++;
        if (ca > 1) puts("");
        vector<vector<int>> stones (n, vector<int> (2, 0));
        for(int i=0; i<n; i++) scanf("%d %d", &stones[i][0], &stones[i][1]);
        vector<vector<float>> dist (n, vector<float> (n, 0.0));
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if (i == j) continue;
                float d = sqrt(1.0*(stones[i][0] - stones[j][0])*(stones[i][0] - stones[j][0]) + 
                               1.0*(stones[i][1] - stones[j][1])*(stones[i][1] - stones[j][1]));
                dist[i][j] = d;
                dist[j][i] = d;
            }
        }
        vector<float> ans (n, 100000000.0);
        priority_queue<pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>> pq;
        pq.push(make_pair(0.0, 0));
        while(!pq.empty() && pq.top().second != 1) {
            float curr = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            for(int v=0; v<n; v++) {
                if (u == v) continue;
                float new_dis = max(curr, dist[u][v]);
                if (new_dis < ans[v]) {
                    ans[v] = new_dis;
                    pq.push(make_pair(new_dis, v));
                }
            }
        }
        printf("Scenario #%d\nFrog Distance = %.3f\n", ca, ans[1]);
    }
    return 0;
}