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

// convert string warehouse to integer code
map<string, int> house;
for (int j=0; j<M; j++){
string k;
cin >> k;

house[k] = j;
}

for (int j=0; j<N; j++){
string A, B;
cin >> A >> B;

}

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();
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;
}
```