ZeroJudge 解題筆記：c187. 10986 - Sending email

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


ZeroJudge 題目連結：c187. 10986 - Sending email

解題想法

這題要求從起點 $S$ 到終點 $T$ 的最短距離，可以用戴克斯特拉演算法 (Dijkstra's algorithm) 解題。

Python 程式碼

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

import sys, heapq

result = []  # 要輸出的結果
T = int(sys.stdin.readline())  # T 組測資
for t in range(1, T+1):  # 執行 T 次
    n, m, start, end = map(int, input().split())  # n 個節點，m 條邊，起點、終點
    if start == end:  # 特例，起點等於終點
        result.append(f"Case #{t:d}: 0\n")  # 答案 0
        for _ in range(m): _ = sys.stdin.readline()  # 依然要讀取以下 m 行測資
    else:  # 一般的狀況
        graph = dict()  # 節點連接關係
        for _ in range(m):  # 讀取 m 行測資
            u, v, w = map(int, sys.stdin.readline().split())  # 節點 u, v 相連，邊長 w
            if u not in graph: graph[u] = [(v, w)]
            else: graph[u].append((v, w))
            if v not in graph: graph[v] = [(u, w)]
            else: graph[v].append((u, w))
        cost = [float('inf')]*n  # 走到每個節點的最低成本
        pq = [(0, start)]  # 最小優先佇列，放入 (0, 起點)
        while pq and pq[0][1] != end:  # 如果 pq 還有資料而且最上面的資料不是終點
            curr, u = heapq.heappop(pq)  # 取出 pq 最上面的資料
            if u not in graph: continue  # 如果 u 沒有子節點，找下一個點
            for v, w in graph[u]:  # 依序讀取 u 的子節點及權重
                new_w = curr + w  # 新的成本
                if new_w < cost[v]:  # 如果比原來走到 v 的最低成本還低
                    cost[v] = new_w  # 更新 cost[v]
                    heapq.heappush(pq, (new_w, v))  # (new_w, v) 加入 pq
          # 如果 cost[end] 不等於預設值，可以走到終點
        ans = str(cost[end]) if cost[end] != float('inf') else "unreachable"
        result.append(f"Case #{t:d}: {ans:s}\n")
sys.stdout.write("".join(result))

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

def solve():
    import sys, heapq

    result = []  # 要輸出的結果
    data = sys.stdin.read().split()
    T = int(data[0])  # T 組測資
    ptr = 1
    for t in range(1, T+1):  # 執行 T 次
        n, m, start, end = map(int, data[ptr:ptr+4])  # n 個節點，m 條邊，起點、終點
        ptr += 4
        if start == end:  # 特例，起點等於終點
            result.append(f"Case #{t:d}: 0\n")  # 答案 0
            for _ in range(m): ptr += 3  # 依然要讀取以下 m 行測資
        else:  # 一般的狀況
            graph = dict()  # 節點連接關係
            for _ in range(m):  # 讀取 m 行測資
                u, v, w = map(int, data[ptr:ptr+3])  # 節點 u, v 相連，邊長 w
                ptr += 3
                if u not in graph: graph[u] = [(v, w)]
                else: graph[u].append((v, w))
                if v not in graph: graph[v] = [(u, w)]
                else: graph[v].append((u, w))
            cost = [float('inf')]*n  # 走到每個節點的最低成本
            pq = [(0, start)]  # 最小優先佇列，放入 (0, 起點)
            while pq and pq[0][1] != end:  # 如果 pq 還有資料而且最上面的資料不是終點
                curr, u = heapq.heappop(pq)  # 取出 pq 最上面的資料
                if u not in graph: continue  # 如果 u 沒有子節點，找下一個點
                for v, w in graph[u]:  # 依序讀取 u 的子節點及權重
                    new_w = curr + w  # 新的成本
                    if new_w < cost[v]:  # 如果比原來走到 v 的最低成本還低
                        cost[v] = new_w  # 更新 cost[v]
                        heapq.heappush(pq, (new_w, v))  # (new_w, v) 加入 pq
            # 如果 cost[end] 不等於預設值，可以走到終點
            ans = str(cost[end]) if cost[end] != float('inf') else "unreachable"
            result.append(f"Case #{t:d}: {ans:s}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

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

int main() {
    int T; scanf("%d", &T);  // T 組測資
    for(int t=1; t<=T; t++) {  // 執行 T 次
        int n, m, start, end;  // n 個節點，m 條邊，起點、終點
        scanf("%d %d %d %d", &n, &m, &start, &end);
        if (start == end) {  // 特例，起點等於終點
            printf("Case #%d: 0\n", t);
            for(int i=0; i<m; i++) {  // 依然要讀取以下 m 行測資
                int u, v, w;  // 節點 u, v 相連，邊長 w
                scanf("%d %d %d", &u, &v, &w);
            }
        } else {  // 一般的狀況
            map<int, vector<pair<int, int>>> graph;  // 節點連接關係
            for(int i=0; i<m; i++) {  // 依然要讀取以下 m 行測資
                int u, v, w;  // 節點 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);  // 走到每個節點的最低成本
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
            pq.push(make_pair(0, start));  // 最小優先佇列，放入 (0, 起點)
            while(!pq.empty() && pq.top().second != end) {  // 如果 pq 還有資料而且最上面的資料不是終點
                int curr = pq.top().first, u = pq.top().second;  // 取出 pq 最上面的資料
                pq.pop();
                if (graph[u].empty()) continue;  // 如果 u 沒有子節點，找下一個點
                for(auto it : graph[u]) {  // 依序讀取 u 的子節點及權重
                    int v = it.first, w = it.second;
                    int new_w = curr + w;  // 新的成本
                    if (new_w < cost[v]) {  // 如果比原來走到 v 的最低成本還低
                        cost[v] = new_w;  // 更新 cost[v]
                        pq.push(make_pair(new_w, v));  // (new_w, v) 加入 pq
                    }
                }
            }
            // 如果 cost[end] 不等於預設值，可以走到終點
            printf("Case #%d: ", t);
            if (cost[end] != 1000000000) printf("%d\n", cost[end]);
            else puts("unreachable");
        }
    }
    return 0;
}