ZeroJudge 解題筆記：d282. 11015 - 05-2 Rendezvous

作者：王一哲
日期：2026年5月30日


ZeroJudge 題目連結：d282. 11015 - 05-2 Rendezvous

解題想法

這題考 Dijkstra's algorithm，先找出以節點 $k$ 為中繼點，從節點 $i$ 走到節點 $j$ 的成本，更新 $i$ 到 $j$ 的最低成本。

Python 程式碼

使用時間約為 15 ms，記憶體約為 8.8 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    ca = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        if n == 0 and m == 0: break
        ca += 1
        # 讀取名字
        names = []
        for _ in range(n):
            names.append(data[ptr])
            ptr += 1
        # 初始化距離矩陣
        dp = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for _ in range(m):
            u = int(data[ptr])
            v = int(data[ptr+1])
            w = int(data[ptr+2])
            ptr += 3
            u -= 1
            v -= 1
            dp[u][v] = w
            dp[v][u] = w
        # Dijkstra's algorithm
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        # 找最低成本
        ans, imin = 0, float('inf')
        for i in range(n):
            cost = sum(dp[i][j] for j in range(n))
            if cost < imin:
                imin = cost
                ans = i
        result.append(f"Case #{ca:d} : {names[ans]}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, ca = 0;
    while(cin >> n >> m && (n != 0 || m != 0)) {
        /* 讀取測資，建立 Dijkstra's algorithm 需要的二維陣列 */
        ca++;
        string names[n];
        for(int i=0; i<n; i++) cin >> names[i];
        vector<vector<int>> dp (n, vector<int> (n, INT_MAX));
        for(int i=0; i<n; i++) {
            dp[i][i] = 0;
        }
        for(int i=0; i<m; i++) {
            int u, v, w; cin >> u >> v >> w;
            u--; v--;
            dp[u][v] = w;
            dp[v][u] = w;
        }
        /* Dijkstra's algorithm 找節點 i 到 j 的最低成本 */
        for(int k=0; k<n; k++) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        int ans = -1, imin = INT_MAX;
        for(int i=0; i<n; i++) {
            int cost = 0;
            for(int j=0; j<n; j++) {
                cost += dp[i][j];
            }
            if (cost < imin) {
                imin = cost;
                ans = i;
            }
        }
        cout << "Case #" << ca << " : " << names[ans] << "\n";
    }
    return 0;
}