UVa 383 Shipping Routes

想法：
　　用BFS來做，前M個先將輸入的字串用map對應成整數，然後接下來N行每行讀兩個字串，將彼此加入可到達的路徑裡，最後P行每行用BFS搜尋路徑。

注意輸出DATA SET"  "1  有兩個空格

	#include <iostream>
	#include <string>
	#include <map>
	#include <vector>
	#include <queue>
	#include <cstdio>
	using namespace std;
	struct route_type{
	vector<string> route;
	};
	int BFS(string Start, string End, map<string,int> &mapping, route_type A[])
	{
	int step[1001] = {0};
	queue<string> Q;
	Q.push(Start);
	while (!Q.empty()) {
	string cur = Q.front();
	Q.pop();
	for (string nxt : A[mapping[cur]].route){
	if (step[mapping[nxt]] == 0) {
	step[mapping[nxt]] = step[mapping[cur]] + 1;
	if (nxt == End) return step[mapping[nxt]];
	Q.push(nxt);
	}
	}
	}
	return 0;
	}
	int main()
	{
	//freopen("input","rt",stdin);
	ios::sync_with_stdio(false);
	int T,Case = 1;
	int M, N, P;
	cin >> T;
	cout << "SHIPPING ROUTES OUTPUT" << endl << endl;
	while (T--) {
	cin >> M >> N >> P;
	map<string,int> mapping;
	string s1,s2;
	for (int i=0; i<M; ++i){
	cin >> s1;
	mapping[s1] = i;
	}
	route_type A[1000];
	for (int i=0; i<N; ++i){
	cin >> s1 >> s2;
	A[mapping[s1]].route.push_back(s2);
	A[mapping[s2]].route.push_back(s1);
	}
	cout << "DATA SET " << Case++ << endl << endl;
	int Size;
	for (int i=0; i<P; ++i){
	cin >> Size >> s1 >> s2;
	int legs = BFS(s1,s2,mapping,A);
	if (!legs) cout << "NO SHIPMENT POSSIBLE" << endl;
	else cout << '$' << Size * legs * 100 << endl;
	}
	cout << endl;
	}
	cout << "END OF OUTPUT" << endl;
	return 0;
	}

view raw [UV] 383 Shipping Routes.cpp hosted with ❤ by GitHub