ZeroJudge A586: 捷運計價問題

題目敘述

每筆測資第一行有一個正整數N，接下來會有N行，每行有兩個字串a和b，代表a和b兩站是連通的。最後會有兩個字串代表起點跟終點。基本價錢是10元，每搭3站要加5元，換一次線也要5元。要求輸出從起點搭車到終點最低的價格是多少。

範例輸入 #1

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

範例輸出 #1

20

範例輸入 #2

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

範例輸出 #2

20

解題思路

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

解題程式碼如下 (僅供參考)：

#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";
}