UVA-762 ( WE SHIP CHEAP ) (Category : BFS)

Problem link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=703

Solution :

#include<bits/stdc++.h>

using namespace std;

map<string,long long int>mp;
vector<long long int>v[1000];

long long int visited[1000];
long long int parent[1000];

vector<string>w;
vector<long long int>c;

void bfs(long long int s,long long int d)
{
    if(s==-30||d==-30)
    {
        cout<<"No route"<<endl;
        return;
    }
    memset(visited,-1,sizeof(visited));
    memset(parent,-1,sizeof(parent));

    long long  int u,p;

    queue<long long int>q;

    q.push(s);

    visited[s]=0;

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(long long int i=0; i<v[u].size(); i++)
        {
            p=v[u][i];

            if(visited[p]==-1)
            {
                visited[p]=visited[u]+1;
                parent[p]=u;
                q.push(p);
            }
            if(u==d) break;
        }
    }
    if(visited[d]==-1) cout<<"No route"<<endl;
    else
    {


        long long int r=d;
        c.push_back(r);
        r=parent[r];
        while(r!=s)
        {
            c.push_back(r);
            r=parent[r];
        }
        c.push_back(s);

        reverse(c.begin(),c.end());

        for(long long int i=0; i<(c.size()-1); i++)
        {
            cout<<w[c[i]]<<" "<<w[c[i+1]]<<endl;
        }

    }

}

int main()
{
//freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    long long int t,i,j,k,l=0;
    string a,b;

    while(scanf("%lld",&t)==1)
    {
        if(l>0) cout<<endl;
        l++;
        j=0;

        for(i=0; i<t; i++)
        {
            cin>>a>>b;
            getchar();

            if(mp.find(a)==mp.end())
            {
                mp[a]=j;
                w.push_back(a);
                j++;
            }
            if(mp.find(b)==mp.end())
            {
                mp[b]=j;
                w.push_back(b);
                j++;
            }
            v[mp[a]].push_back(mp[b]);
            v[mp[b]].push_back(mp[a]);
        }
        cin>>a>>b;

        if(mp.find(a)==mp.end()) mp[a]=-30;
        if(mp.find(b)==mp.end()) mp[b]=-30;


        bfs(mp[a],mp[b]);

        mp.clear();
        c.clear();
        w.clear();
        for( i=0; i<1000; i++) v[i].clear();
    }


}