## Tuesday, December 23, 2014

### UVa Problem 383 - Shipping Routes

Problem:

Solution:

Single source shortest path without weight, easily solved by breadth first search

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=319

#include "UVa383.h"

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int UVa383()
{
cout << "SHIPPING ROUTES OUTPUT" << endl << endl;
int num_test_cases;
cin >> num_test_cases;
for (int test_case_number = 1; test_case_number <= num_test_cases; test_case_number++)
{
cout << "DATA SET  " << test_case_number << endl << endl;
int num_warehouses;
cin >> num_warehouses;
int num_legs;
cin >> num_legs;
int num_requests;
cin >> num_requests;
map<string, int> numbering;
map<int, string> naming;
for (int w = 0; w < num_warehouses; w++)
{
string name;
cin >> name;
int number = numbering.size();
numbering.insert(pair<string, int>(name, number));
naming.insert(pair<int, string>(number, name));
}

for (int l = 0; l < num_legs; l++)
{
string w1;
string w2;

cin >> w1;
cin >> w2;
}

for (int r = 0; r < num_requests; r++)
{
int size;
string w1;
string w2;

cin >> size;
cin >> w1;
cin >> w2;

int wn1 = numbering[w1];
int wn2 = numbering[w2];

vector<int> distance;
queue<int> bfs_queue;
distance.resize(num_warehouses);
for (int w = 0; w < num_warehouses; w++)
{
distance[w] = -1;
}

distance[wn1] = 0;
bfs_queue.push(wn1);

while (bfs_queue.size() > 0)
{
int visiting = bfs_queue.front();
bfs_queue.pop();
{
int neighbor = *ni;
if (distance[neighbor] == -1)
{
distance[neighbor] = distance[visiting] + 1;
bfs_queue.push(neighbor);
}
}
}

if (distance[wn2] == -1)
{
cout << "NO SHIPMENT POSSIBLE" << endl;
}
else
{
cout << "\$" << size * distance[wn2] * 100 << endl;
}
}

cout << endl;
}

cout << "END OF OUTPUT" << endl;

return 0;
}