UVa 762 We Ship Cheap

想法：
        用BFS從起點搜尋終點，並用visit[]儲存步數，然後再從終點依據visit走回起點，並將過程走過的點儲存起來，最後輸出。

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

view raw [UVa] 762 We Ship Cheap.cpp hosted with ❤ by GitHub