762 – We Ship Cheap UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=703

Graphs, Breadth First Search, Single source shortest path(SSSP).

How I did it

• Read the number of cities that has an edge.
• Read the origen and destination city.
• Set the graph.
• If origen and destination are present in the graph call bfs. Otherwise print No route.
• If distance of destination is -1(No reachable from origen) cal find path.
• Print the path.

Hints

• I got 4 runtime errors. The origen and destination cities are not necessarily in the graph

Input

3
JV PT
KA PT
KA HP
JV HP

2
JV PT
KA HP
JV HP

0
AA BB

1
AA BB
CC BB

1
AA BB
GG PP

2
AA BB
BB CC
GG GG

4
AB JK
PO LK
QW PO
LK AB
AB PO

Output

JV PT
PT KA
KA HP

No route

No route

No route

No route

AB LK
LK PO

Code

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

using namespace std;

map <int, vector <int> > graph;
map<int,bool> discovered;//keeps track if a node has been reached
map<int,int>  parent;//stores the nodes ancestor that discovered it for the first time
map<int,int>  distances;//stores the distance to reach each node from the source
//For read the data
vector<pair<string,string> > edgesVec;
set<string> mySet;
map<string,int> vec;
vector<string> output;
vector<int> outputId;

void readEdges(int edges)
{
    string c1, c2;
    for(int x=1; x<=edges; x++)
    {
        cin>>c1>>c2;
        pair<string,string> p = make_pair(c1,c2);
        edgesVec.push_back(p);
        mySet.insert(c1);mySet.insert(c2);
    }
}

void setId()
{
    int index = 0;
    for(set<string>::iterator it=mySet.begin(); it!=mySet.end(); it++, index++)
        vec[*it] = index;
}

void read_graph()
{
    //graph.clear();
    int i, vertex1, vertex2;
    string el1, el2;
    for(i = 0; i < edgesVec.size(); i++)
    {
        el1 = edgesVec[i].first;
        el2 = edgesVec[i].second;
        vertex1 = vec[el1];
        vertex2 = vec[el2];

        graph[vertex1].push_back(vertex2);
        graph[vertex2].push_back(vertex1);

        discovered[vertex1] = false;discovered[vertex2] = false;
        parent[vertex1] = -1;parent[vertex2] = -1;
        distances[vertex1] = -1;distances[vertex2] = -1;
    }
}

void clearGraph()
{
    graph.clear();
    discovered.clear();//keeps track if a node has been reached
    parent.clear();//stores the nodes ancestor that discovered it for the first time
    distances.clear();//stores the distance to reach each node from the sour
    edgesVec.clear();
    mySet.clear();
    vec.clear();
    output.clear();
    outputId.clear();
}

void bfs(int start)
{
    int current;//current node being processed
    int next;//reached node by current
    unsigned int i;
    queue<int> vertices;//vertices to process
    distances[start] = 0;
    discovered[start] = true;
    vertices.push(start);
    while(!vertices.empty())
    {
        current = vertices.front();
        vertices.pop();
        for(i = 0; i < graph[current].size(); i++)//for each node connected to current
        {
            next = graph[current][i];
            if(!discovered[next])//if it hasn't been reached
            {
                discovered[next] = true;//mark it as reached
                parent[next] = current;//store its parent
                distances[next] = distances[current]+1;//save the distance
                vertices.push(next);//push it to the queue for further analysis
            }
        }
    }
}

void find_path(int vertex)//recursive procedure to find the path
{
    if(vertex == -1)
        return;
    find_path(parent[vertex]);
    for(map<string,int>::iterator it=vec.begin(); it!=vec.end(); it++)
    {
        if(it->second == vertex)
        {
            output.push_back(it->first);
            break;
        }
    }
    //printf("%d ", vertex);
}

int main()
{
    int edges, flag = 0;
    string c1,c2;
    int origen, destino;
    while(scanf("%d", &edges) != EOF)
    {
        readEdges(edges);
        setId();
        read_graph();
        cin>>c1>>c2;

        if(!flag)
           flag = 1;
        else
            printf("*\n");

        map<string,int>::iterator iter1, iter2;
        iter1 = vec.find(c1);
        iter2 = vec.find(c2);

        if(iter1 == vec.end() || iter2 == vec.end())
           printf("No route\n");
        else
        {
            origen  = vec[c1];
            destino = vec[c2];
            bfs(origen);
            if(distances[destino] == -1)
               printf("No route\n");
            else
            {
                find_path(destino);                for(int x=0; x<output.size(); x++)
                {
                    if(x == 0)
                       cout<<output[x]<<" ";
                    else if(x == output.size()-1)
                        cout<<output[x]<<endl;
                    else
                        cout<<output[x]<<endl<<output[x]<<" ";
                }
            }
        }
        clearGraph();
    }
return 0;
}