UVA 762 - We Ship Cheap(cpp file)

Problem Type : Graph (BFS)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#define MAX 1112
#define max1 1112
using namespace std;
int color[max1],mat[MAX][MAX],mat1[MAX][MAX],par[max1],start,end1,store[MAX];
map<string,int> mymap;
map<int,string>mymap1;
void bfs(int start,int end1)
{
    int i,j,vx;
    queue<int>Q;
    Q.push(start);
    color[start]=1;
    par[start]=start;
    while(!Q.empty())
    {
        vx=Q.front();
        Q.pop();
        for(i=1; i<=mymap.size(); i++)
        {
            if(mat[vx][i]==1 && color[i]==0)
            {
                color[i]=1;
                par[i]=vx;
                Q.push(i);
            }
        }

    }
}
int main()
{
    int i,j,k,len,n,node,c=0;
    string node1,node2;
    while(scanf("%d",&n)==1)
    {
        if(c>0)
            printf("\n");
        c++;
        node=0;
        for(i=1; i<=n; i++)
        {
            cin >> node1 >> node2;

            if(mymap.find(node1)==mymap.end())
            {
                node=node+1;
                mymap[node1]= node;
            }
            if(mymap1.find(node)==mymap1.end())
            {
                mymap1[node]=node1;
            }
            if(mymap.find(node2)==mymap.end())
            {
                node=node+1;
                mymap[node2]= node;
            }
            if(mymap1.find(node)==mymap1.end())
            {
                mymap1[node]=node2;
            }
            int x =mymap[node1];
            int y =mymap[node2];
            mat[x][y]=1;
            mat[y][x]=1;


        }
        cin >> node1;

        cin >> node2;
        start =0;
        end1=0;
        start=mymap.find(node1)->second;
        end1=mymap.find(node2)->second;
        if(start >0 && end1>0)
            bfs(start,end1);
        else
        {
            printf("No route\n");
            goto D;
        }
        if(color[end1]==1)
        {
            k=end1;
            for(i=0; ; i++)
            {
                store[i]=par[k];
                if(store[i]==start)
                    break;
                k=store[i];
            }
            for(j=i; j>=0; j--)
            {
                cout << mymap1[store[j]] << " ";
                if(j!=0)
                    cout << mymap1[store[j-1]] << '\n';
            }
            cout << mymap1[end1] << '\n';
        }
        else if(color[end1]==0 )
        {
            printf("No route\n");
        }

D:
        mymap.clear();
        mymap1.clear();
        memset(color,0,sizeof(color));
        memset(mat,0,sizeof(mat));
        memset(par,0,sizeof(par));

    }
}