UVA – 383 – Shipping Routes


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>


using namespace std;
#define MAX 40
int Index = 1;


int main() {

	int N, E, S, T,CASE =1;

	bool g[MAX][MAX];

	cout << "SHIPPING ROUTES OUTPUT\n" << endl;
	cin >> T;

	while (T--) {
		cin >> N >> E >> S;

		Index = 1;
		map<string, int> m;

		for (int i = 0; i < MAX; i++)
			memset(g[i], 0, sizeof(g[i]));

		while (N--) {
			string nodeName;
			cin >> nodeName;
			m[nodeName] = Index++;
		}

		while (E--) {
			string a, b;
			cin >> a >> b;

			 g[m[a]][m[b]]  = g[m[b]][m[a]] = true;
		}

		printf("DATA SET  %d\n\n", CASE++);
		while (S--) {
			int price;
			string source , b;
			cin >> price >> source >> b;


			int distance[40];

			memset(distance, -1, sizeof distance);

			distance[m] = 0;

			queue<int> que;
			que.push(m);

			while (!que.empty()) {
				int node = que.front();
				que.pop();
				for (int i = 1; i < Index; i++)
					if (distance[i] == -1 && g[node][i]) {
						que.push(i);
						distance[i] = distance[node] + 1;
					}
			}


			int ans = distance[m[b]]*100*price;

			if(ans <-1)
				cout << "NO SHIPMENT POSSIBLE"  << endl;
			else
				cout << "$" << ans << endl;


		}

		cout << endl;

	}
	cout << "END OF OUTPUT" << endl;
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: