ZeroJudge 解題筆記：g422. PD.紅血球的快遞任務

作者：王一哲
日期：2025年11月5日


ZeroJudge 題目連結：g422. PD.紅血球的快遞任務

解題想法

這題考 Dijkstra’s Shortest Path Algorithm。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 37.9 MB，通過測試。

import heapq

n, m, t = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))
cost = [float('inf')]*n
cost[0] = 0
pq = [(0, 0)]  # (cost, node)
while pq:
    cur_cost, u = heapq.heappop(pq)
    if u == t: break  # 已經走到終點
    if cur_cost > cost[u]: continue  # 如果已經找到比較低的成本，找下一筆資料
    for v, w in graph[u]:  # 依序取出 u 的子節點 v、成本 w
        if cost[u] + w < cost[v]:  # 如果從 u 走到 v 的成本較低
            cost[v] = cost[u] + w
            heapq.heappush(pq, (cost[v], v))
print(cost[t])

C++ 程式碼

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

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

int main() {
    int n, m, t; scanf("%d %d %d", &n, &m, &t);
    vector<vector<pair<int, int>>> graph (n);
    for(int i=0; i<m; i++) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }
    vector<int> cost (n, 1000000000);
    cost[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // (cost, node)
    pq.push(make_pair(0, 0));
    while(!pq.empty()) {
        int cur_cost = pq.top().first, u = pq.top().second; pq.pop();
        if (u == t) break;  // 已經走到終點
        if (cur_cost > cost[u]) continue;  // 如果已經找到比較低的成本，找下一筆資料 
        for(auto it : graph[u]) {  // 依序取出 u 的子節點 v、成本 w
            int v = it.first, w = it.second;
            if (cost[u] + w < cost[v]) {  // 如果從 u 走到 v 的成本較低
                cost[v] = cost[u] + w;
                pq.push(make_pair(cost[v], v));
            }
        }
    }
    printf("%d\n", cost[t]);
    return 0;
}