ZeroJudge 解題筆記：a586. 4. 捷運計價問題

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


ZeroJudge 題目連結：a586. 4. 捷運計價問題

解題想法

我用 BFS 解題，由於這題可以用不同的走法到達同一座車站，不能用是否已走訪這座車站來排除重複的走法。改用一個字典 prices 儲存由起點到達各車站的最低票價，如果經由現在的路線走到這座車站的票價大於目前已知的最低票價，代表這個走法走到終點時不可能是新的最低票價，不需要加入待走訪佇列 que 之中。由於 que 要儲存的資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)，有 1 個字串及 3 個整數，在 C++ 我另外定義 struct Station 儲存資料。

Python 程式碼

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

from collections import defaultdict, deque

n = int(input())  # 接下來有 n 行
graph = defaultdict(list)  # 車站連接方式，無向圖
for _ in range(n):
    u, v = input().split()
    graph[u].append(v)
    graph[v].append(u)
start, end = input().split()  # 起點、終點
if start == end:  # 特例，起點、終點相同
    print(10)  # 最低票價 10 元
else:
    # 到各車站所需最低票價，預設為無窮大
    prices = defaultdict(lambda : float('inf'))
    prices[start] = 10  # 到起點票價 10 元
    # 待走訪佇列，資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)
    que = deque([(start, 10, 0, 0)])
    while que:  # 用 BFS 找走到終點的最低票價
        curr, fee, cnt, trans = que.popleft()
        if curr == end:  # 走到終點
            prices[end] = min(prices[end], fee)  # 更新走到終點的最低票價
            continue  # 找下一個點，可能有其它更低票價的走法
        if fee > prices[end]:  # 目前票價大於已知到達終點的最低票價
            continue  # 找下一個點，不可能是新的最低票價
        for nxt in graph[curr]:  # 依序讀取相連的車站
            new_cnt = cnt + 1  # 經過站數加 1
            if nxt[0] != curr[0]: new_trans = trans + 1  # 轉乘不同路線
            else: new_trans = trans
            new_fee = 10 + new_cnt//3*5 + new_trans*5  # 新的票價
            if new_fee > prices[nxt]:  # 到達此站的票價超過已知的最低票價
                continue  # 找下一個點，不可能是新的最低票價
            prices[nxt] = new_fee
            que.append((nxt, new_fee, new_cnt, new_trans))
    print(prices[end])

C++ 程式碼

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

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

struct Station {  // 車站資訊
    string name;  // 編號
    int fee, cnt, trans;  // 目前的票價, 經過站數, 轉乘路線數
    
    Station(string s, int a, int b, int c) : name(s), fee(a), cnt(b), trans(c) {}  // 建構子
    Station(string s) : name(s), fee(10), cnt(0), trans(0) {}  // 重載建構子
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 接下來有 n 行
    map<string, vector<string>> graph;  // 車站連接方式，無向圖
    map<string, int> prices;  // 到各車站所需最低票價，預設為無窮大
    for(int i=0; i<n; i++) {
        string u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        prices[u] = 1000000000;
        prices[v] = 1000000000;
    }
    string start, end; cin >> start >> end;  // 起點、終點
    if (start == end) {  // 特例，起點、終點相同
        cout << "10\n";  // 最低票價 10 元
    } else {
        prices[start] = 10;  // 到起點票價 10 元
        // 待走訪佇列，資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)
        queue<Station> que;
        Station start_station(start);
        que.push(start_station);
        while(!que.empty()) {  // 用 BFS 找走到終點的最低票價
            Station curr = que.front();
            que.pop();
            if (curr.name == end) {  // 走到終點
                prices[end] = min(prices[end], curr.fee);  // 更新走到終點的最低票價
                continue;  // 找下一個點，可能有其它更低票價的走法
            }
            if (curr.fee > prices[end]) {  // 目前票價大於已知到達終點的最低票價
                continue;  // 找下一個點，不可能是新的最低票價
            }
            for(string nxt : graph[curr.name]) {  // 依序讀取相連的車站
                int new_cnt = curr.cnt + 1;  // 經過站數加 1
                int new_trans = curr.trans;  // 轉乘次數
                if (nxt[0] != curr.name[0]) new_trans++;  // 轉乘不同路線
                int new_fee = 10 + new_cnt/3*5 + new_trans*5;  // 新的票價
                if (new_fee > prices[nxt]) {  // 到達此站的票價超過已知的最低票價
                    continue;  // 找下一個點，不可能是新的最低票價
                }
                prices[nxt] = new_fee;
                Station nxt_station (nxt, new_fee, new_cnt, new_trans);
                que.push(nxt_station);
            }
        }
        cout << prices[end] << "\n";
    }
    return 0;
}