[UV] 383 Shipping Routes.cpp

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