383 - Shipping Routes

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cstring>
#define M 650
using namespace std;

bool list[M][M];
char Node[M][10];

int FindID(char[],int N);
int BFS(int,int,int);

int main()
{
    int t,i,k,m,n,p,xid,yid,ls,ss;
    char X[3],Y[3];
    //freopen("in.txt","r",stdin);
    printf("SHIPPING ROUTES OUTPUT\n\n");

    scanf("%d",&t);
    for(k=1;k<=t;k++)
    {
        memset(list,false,sizeof(list));
        memset(Node,'\0',sizeof(Node));

        scanf("%d%d%d\n",&m,&n,&p);
        for(i=0;i<m;i++)
            scanf("%s",Node[i]);

        for(i=0;i<n;i++)
        {
            scanf("%s%s",X,Y);
            xid=FindID(X,m);
            yid=FindID(Y,m);

            list[xid][yid]=list[yid][xid]=true;
        }

        printf("DATA SET  %d\n\n",k);

        for(i=0;i<p;i++)
        {
            scanf("%d%s%s",&ss,X,Y);
            xid=FindID(X,m);
            yid=FindID(Y,m);

            if(xid==yid)
            {
                printf("$0\n");
                continue;
            }

            ls = BFS(xid,yid,m);

            if(ls<0)
                printf("NO SHIPMENT POSSIBLE\n");
            else
                printf("$%d\n",ls*ss*100);
        }
        printf("\n");
    }
    printf("END OF OUTPUT\n");
    return 0;
}

int FindID(char node[],int N)
{
    int i;
    for(i=0;i<N;i++)
        if(Node[i][0]==node[0]&&Node[i][1]==node[1])
            return i;
    return -1;
}

int BFS(int x,int y,int N)
{
    int i,h;
    int color[M],d[M];
    queue<int>Q;
    memset(color,0,sizeof(color));

    color[x]=1;d[x]=0;
    Q.push(x);
    while(!Q.empty())
    {
        h=Q.front();Q.pop();

        for(i=0;i<N;i++)
        {
            if(list[h][i]&&color[i]==0)
            {
                d[i]=d[h]+1;
                color[i]=1;
                if(i==y)return d[y];
                Q.push(i);
            }
        }
    }
    return -1;
}