[UVa] 762 We Ship Cheap.cpp

#include <bits/stdc++.h>
using namespace std;

map<string, int> Map;  //將每個點從字串換成編號
vector<string> toPoint[10001];  // 用來存每個點能連到哪些點

void BFS(string Start, string End)
{
    queue<string> Q;
    Q.push(Start);
    int visit[10001] = {0};
    visit[Map[Start]] = 1;

    string cur;
    bool findedEnd = 0;
    while (!Q.empty() && !findedEnd) {  // BFS演算法
        cur = Q.front();
        Q.pop();

        for (string &nxt : toPoint[Map[cur]]) {
            if (visit[Map[nxt]] == 0) {
                visit[Map[nxt]] = visit[Map[cur]] + 1;
                if (nxt == End){
                    findedEnd = 1;
                    break;
                }
                Q.push(nxt);
            }
        }
    }
    // 從終點逆向走回起點，並將過程存在ans裡
    int step_count = visit[Map[End]];
    cur = End;
    vector<string> ans;
    ans.push_back(End);
    bool stop = 0;
    while (!stop) {
        bool finded_nxt_point = 0;
        for (string &nxt : toPoint[Map[cur]]) {
            if (nxt == Start) {
                ans.push_back(Start);
                stop = 1;
                break;
            }
            if (visit[Map[nxt]] == step_count - 1) {
                --step_count;
                ans.push_back(nxt);
                cur = nxt;
                finded_nxt_point = 1;
                break;
            }
        }
        if (!finded_nxt_point) stop = 1;
    }
    if (visit[Map[End]] == 0) cout << "No route" << endl;
    else {
        for (int i = ans.size() - 1; i > 0; --i)
            cout << ans[i] << ' ' << ans[i-1] << endl;
    }
}
int main()
{
 //   freopen("input.txt","rt",stdin);
    ios::sync_with_stdio(false);
    int N, blank_line = 0;
    while (cin >> N) {
        if (blank_line) cout << endl;
        blank_line = 1;
        Map.clear();
        for (auto &v : toPoint) v.clear();

        string p1, p2;
        for (int i = 0, j = 1; i < N; ++i) {
            cin >> p1 >> p2;
            if (!Map[p1]) Map[p1] = j++;
            if (!Map[p2]) Map[p2] = j++;
            toPoint[Map[p1]].push_back(p2);
            toPoint[Map[p2]].push_back(p1);
        }
        cin >> p1 >> p2;
        //p1,p2不管是否為前面儲存的點，如果p1==p2就輸出p1 p2
        if (p1 == p2) cout << p1 << ' ' << p2 << endl;
        else if (!Map[p1] || !Map[p2]) cout << "No route" << endl;
        else BFS (p1, p2);
    }
}