ZeroJudge 解題筆記：c128. 00544 - Heavy Cargo

作者：王一哲
日期：2026年3月20日


ZeroJudge 題目連結：c128. 00544 - Heavy Cargo

解題想法

這題跟 c125. 00534 - Frogger。 依序讀取兩座城市的名稱及道路的承受重量上限，城市之間連接的關係存入字典 graph，key 為城市的名稱，value 為連接的城市名稱，格式為 list；道路資料存入字典 edge，key 為兩座城市 $u, v$ 組成的 tupel，value 為重量，因為是無向圖，$(u, v), (v, u)$ 都要存資料。 開一個陣列 $ans$，儲存到達第 $i$ 座城市的路徑可以承受的最大重量的最小值。接下來用一個最大優先佇列 $pq$，資料為 $(重量, 城市名稱)$，代表到第 $i$ 座城市的路徑上某一條路可以承受的最大重量，重量大的資料放上面。因為 Python 的 heapq 是最小優先佇列，為了把最大值放在上面，重量要加負號。如果 $pq$ 還有資料，而且 $pq$ 最上面的城市不等於終點，while 迴圈繼續執行。每次取出 $pq$ 最上方的資料，目前的重量 $curr$、城市的名稱 $u$，掃過與 $u$ 相連的城市 $v$，取 $curr$ 與 $edge[u, v]$ 較小者為新的重量 $new_w$，如果 $new_w < ans[v]$，更新 $ans[v]$，並將 ${new_w, v}$ 加入 $pq$。

Python 程式碼

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

import sys, heapq

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n, r = map(int, line.split())  # n 個城市，r 條道路
    if n == 0 and r == 0: break  # 中止迴圈的條件
    ca += 1  # 測資編號加 1
    graph, edge = dict(), dict()  # 城市連接的關係，道路可以承受的重量
    for _ in range(r):  # 讀取 r 條道路
        u, v, w = sys.stdin.readline().split()  # 城市 u、v 之間的道路可以承受重量 w
        w = int(w)  # w 轉成 int
        if u not in graph: graph[u] = [v]  # 如果 u 不在 graph 之中，設定為 [v]
        else: graph[u].append(v)  # 反之，加上 v
        if v not in graph: graph[v] = [u]  # 如果 v 不在 graph 之中，設定為 [u]
        else: graph[v].append(u)  # 反之，加上 u
        edge[u, v] = w  # u、v 之間的道路可以承受重量 w
        edge[v, u] = w
    ans = {k: 0 for k in graph.keys()}  # 走到每個城市的路上可以承受的重量最大值
    start, end = sys.stdin.readline().split()  # 起點、終點
    pq = [(-float('inf'), start)]  # (-重量, 城市)，加負號讓重量大的放上面
    while pq and pq[0][1] != end:  # 如果 pq 有資料而且最上面的城市不是終點
        w, u = heapq.heappop(pq)  # 取出 pq 最上面的重量、城市
        w = -w  # w 轉成正值
        for v in graph[u]:  # 依序取出 u 連接的城市 v
            new_w = min(w, edge[u, v])  # 取 w 與 u、v 之間可以承受重量較小者
            if new_w > ans[v]:  # 如果 new_w 是新的最大值
                ans[v] = new_w  # 更新 ans[v]
                heapq.heappush(pq, (-new_w, v))  # (-new_w, v) 加入 pq
    if ca > 1: result.append("\n")  # 如果不是第 1 筆測資，先換行
    result.append(f"Scenario #{ca:d}\n{ans[end]:d} tons\n")  # 答案加入 result
sys.stdout.write("".join(result))

C++ 程式碼

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

#include <iostream>
#include <string>
#include <map>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() { 
    ios::sync_with_stdio(0); cin.tie(0);
    int ca = 0, n, r;  // n 個城市，r 條道路
    while((cin >> n >> r) && (n != 0 || r != 0)) {
        ca++;  // 測資編號加 1
        map<string, vector<string>> graph;  // 城市連接的關係
        map<pair<string, string>, int> edge;  // 道路可以承受的重量
        for(int i=0; i<r; i++) {  // 讀取 r 條道路
            string u, v; int w;  // 城市 u、v 之間的道路可以承受重量 w
            cin >> u >> v >> w;
            graph[u].push_back(v);  // u 可以走到 v
            graph[v].push_back(u);  // v 可以走到 u
            edge[make_pair(u, v)] = w;  // u、v 之間的道路可以承受重量 w
            edge[make_pair(v, u)] = w;
        }
        map<string, int> ans;  // 走到每個城市的路上可以承受的重量最大值
        for(auto it : graph) ans[it.first] = 0;
        string start, end; cin >> start >> end;  // 起點、終點
        priority_queue<pair<int, string>> pq;  // (重量, 城市)，重量大的放上面
        pq.push(make_pair(100000000, start));
        while(!pq.empty() && pq.top().second != end) {  // 如果 pq 有資料而且最上面的城市不是終點
            int w = pq.top().first;  // 取出 pq 最上面的重量、城市
            string u = pq.top().second;
            pq.pop();
            for(string v : graph[u]) {  // 依序取出 u 連接的城市 v
                int new_w = min(w, edge[make_pair(u, v)]);  // 取 w 與 u、v 之間可以承受重量較小者
                if (new_w > ans[v]) {  // 如果 new_w 是新的最大值
                    ans[v] = new_w;  // 更新 ans[v]
                    pq.push(make_pair(new_w, v));  // (new_w, v) 加入 pq
                }
            }
        }
        if (ca > 1) cout << "\n";  // 如果不是第 1 筆測資，先換行
        cout << "Scenario #" << ca << "\n" << ans[end] << " tons\n";
    }
    return 0;
}