[UVa] 10009 All Roads Lead Where?.cpp

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
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;
    // 標準BFS演算法
    string cur;
    bool FindedEnd = 0;
    while (!Q.empty() && !FindedEnd) {
        cur = Q.front();
        Q.pop();

        for (const auto &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]];
    vector<char> Ans = {End[0]};
    cur = End;
    while (step_count != 1) {
        for (const auto &nxt : toPoint[Map[cur]]) {
            if (visit[Map[nxt]] == step_count - 1) {
                Ans.push_back(nxt[0]);
                --step_count;
                cur = nxt;
                break;
            }
        }
    }
    for (auto i = Ans.end() - 1; i != Ans.begin(); --i)
        cout << *i;
    cout << Ans[0] << endl;
}
int main()
{
  //  freopen("input.txt","rt",stdin);
    ios::sync_with_stdio(false);
    int Case, M, N;
    cin >> Case;
    while (Case--) {
        Map.clear();
        for (auto &v : toPoint) v.clear();
        string s1, s2;

        cin >> M >> N;
        for (int i = 0, j = 1; i < M; ++i) {
            cin >> s1 >> s2;
            if (!Map[s1]) Map[s1] = j++;
            if (!Map[s2]) Map[s2] = j++;
            toPoint[Map[s1]].push_back(s2);
            toPoint[Map[s2]].push_back(s1);
        }
        for (int i = 0; i < N; ++i) {
            cin >> s1 >> s2;
            BFS (s1, s2);
        }
        if (Case) cout << endl;
    }
    return 0;
}