Shipping Routes

The Slow Boat to China Shipping company needs a program to help them quickly quote costs to prospective customers. The cost of a shipment depends on the size of the shipment and on how many shipping legs it requires. A shipping leg connects two warehouses, but since every pair of warehouses is not directly connected by a leg, it might require more than one leg to send a shipment from one warehouse to another.

A data set can represent from 1 to 30 warehouses. A two-letter code name will identify each warehouse (capital letters only). Shipping legs can exist between any two distinct warehouses. All legs are bidirectional.

The cost of a shipment is equal to the size of the shipment times the number of shipping legs required times $100.

The input to the program identifies the warehouse code names and the existence of all shipping legs. For a given shipping request, consisting of the size of the shipment, the source warehouse and the destination warehouse, the program will output the best (cheapest) cost for the shipment, if it is possible to send shipments from the requested source to the requested destination. Alternately, the program must state that the request cannot be fulfilled.

Problem Source : UVa Online Judge

The output format is tedious so I don’t include them here. Anyway, the technique I used in this problem is by changing the string warehouse datatype to int. In my opinion, this is easier for me to mark the distance between warehouses by index.

C++

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
#include <queue>
using namespace std;

int main() {
	
	int T;
	cin >> T;
	
	for (int i=0; i<T; i++){
		int M, N, P;
		cin >> M >> N >> P;
		
		vector<int> adjList[M];
		
		// convert string warehouse to integer code
		map<string, int> house;
		for (int j=0; j<M; j++){
			string k;
			cin >> k;
			
			house[k] = j;
		}
		
		// build adjacency list graph
		for (int j=0; j<N; j++){
			string A, B;
			cin >> A >> B;
			
			adjList[house[A]].push_back(house[B]);
			adjList[house[B]].push_back(house[A]);
		}
		
		for (int j=0; j<P; j++){
			int V; string s, e;
			cin >> V >> s >> e;
			
			int S = house[s];
			int E = house[e];
			
			// prepare dist
			int dist[M];
			memset(dist, -1, sizeof(dist));
			
			// start standard bfs
			queue<int> q;
			q.push(S);
			
			dist[S] = 0;
			
			bool found = false;
			while (!q.empty() && !found){
				int x = q.front(); q.pop();
				for (vector<int>::iterator it = adjList[x].begin(); it != adjList[x].end(); it++){
					if (dist[*it] != -1) continue;
					else if (*it == E){
						dist[*it] = dist[x] + 1;
						found = true;
						break;
					}
					else{
						dist[*it] = dist[x] + 1;
						q.push(*it);
					}
				}
			}
			
			if (dist[E] == -1) cout << "NO SHIPMENT POSSIBLE" << endl;
			else cout << "$" << V*dist[E]*100 << endl;
		}
	}
	
	return 0;
}
Advertisements
Shipping Routes

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