UVa 10009 All Roads Lead Where?

想法：
       將讀進來的字串用map轉成數字，並建立兩個點的連線。
       用BFS演算法來搜索目的地，並在過程中用visit[]記錄每次的步數，最後抵達終點時BFS演算法結束，然後我們再利用visit從終點逆向走回起點，記下這條路徑走過的點，最後輸出結果。

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

view raw [UVa] 10009 All Roads Lead Where?.cpp hosted with ❤ by GitHub