ZeroJudge A586: 捷運計價問題

「天龍國」為了促進觀光，推出捷運觀光地圖。只要持有觀光護照者搭乘捷運將會有特別的優待，並依照下列三種計費規定收費：

  1. 基本票價十元。
  2. 每經過三站票價加五元。
  3. 轉乘不同捷運路線加五元。

以下圖為例，若起點為 B1，終點為 G2，若搭乘路線為： B1-B2-B3-B4-G1-G2，所需票價為 20元(=10+51+5，為基本票價 10元+經過 5站需 5元+轉乘 5元)；若搭乘路線為： B1-B2-R1-R2-R3-G2，所需票價為 25元(=10+51+5*2，為基本票價 10元+經過5站需 5元 +轉乘兩種路線 10元)。

ZeroJudge A586 題目敘述

現在請你設計一個程式，當遊客決定好捷運的起點及終點時，能為每一個來此觀光的遊客計算票價 (若有多條路線可從起點抵達終點時，請計算出最便宜的票價)。

範例測資

範例輸入範例輸出
第一行有一個正整數 N (1 ≤ N ≤ 500)，N 代表接下來有 N 筆目前捷運站的資訊。
自第二行到第 N+1行，每一行代表捷運任意兩站連通的資訊，每一站命名為一個大寫英文字母後接數字，其中開頭的大寫英文字母代表所在路線，數字 m為小於等於 100 的正整數 (1 ≤ M ≤ 100)。此兩站中間以一個空格區分，兩站之間雙向都可以連通。
第 N+2 行代表所要規劃路徑的起點與終點，中間以一個空格區分。		請輸出一個數值，代表規劃的起點到終點之最便宜票價。
11
B1 B2
B2 B3
B3 B4
B4 B5
B4 G1
G1 G2
G2 G3
R1 R2
R2 R3
B2 R1
R3 G2
B1 G2		20
12
R1 R2
R2 R3
R3 R4
R4 R5
R5 R6
R6 R7
R7 B1
R7 Y1
Y1 B1
Y1 R1
Y1 G1
G1 R1
G1 B1		20
ZeroJudge A586 範例測資

解題思路

使用 Map 來紀錄每個車站可以到哪幾個車站，可以使用 Vector 的方式來存車站，因為是雙向的，所以目的地車站也要存說可以到起點車站。使用 BFS 的方式尋找最低金額的路線，可以使用 Map 將每個車站的金額存起來，如果下次有走到相同的車站就進行比較看哪一個方案的金額較低。最後輸出終點車站的 Map 值即可。

範例程式碼－ZeroJudge A586: 捷運計價問題

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int N;
map<string, vector<string>>MAP;
map<string, pair<int, int>>info;

void BFS(vector<string>start)
{
    if (start.size() == 0) return;
    vector<string>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        vector<string>next = MAP[start[i]];
        for (int j = 0; j<next.size(); j++)
        {
            int step = info[start[i]].first+1, line = info[start[i]].second;
            if (start[i][0] != next[j][0]) line++;
            if (info[next[j]].first == 0 && info[next[j]].second == 0)
            {
                info[next[j]].first = step;
                info[next[j]].second = line;
                newStart.push_back(next[j]);
                continue;
            }
            int oldmoney = 5*(info[next[j]].first/3) + 10 + (5*info[next[j]].second);
            int newmoney = 5*(step/3) + 10 + (5*line);
            if (newmoney < oldmoney)
            {
                info[next[j]].first = step;
                info[next[j]].second = line;
                newStart.push_back(next[j]);
                continue;
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        string a, b;
        cin >> a >> b;
        MAP[a].push_back(b);
        MAP[b].push_back(a);
    }
    string start, finish;
    cin >> start >> finish;
    info[start].first = 0;
    info[start].second = 0;
    vector<string>v;
    v.push_back(start);
    BFS(v);
    cout << 5*(info[finish].first/3) + 10 + (5*info[finish].second) << "\n";
}

//ZeroJudge A586
//Dr. SeanXD
標籤

相關文章

發佈留言