OJ Board

Code: Select all

1
1 0 0
AA

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET OUTPUT 1
<one blank line>
<one more blank line>
END OF OUTPUT

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET OUTPUT 1
<one only blank line>
END OF OUTPUT

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET OUTPUT 1
<one only blank line>
END OF OUTPUT

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1
<one blank line>
<one more blank line>
END OF OUTPUT 

Code: Select all

puts( "SHIPPING ROUTES OUTPUT" );
for each case
    printf( "\nDATA SET %2d\n\n", cs++ );
    for each query
        print necessary output
puts( "\nEND OF OUTPUT" );

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1 (there are two spaces after the word SET)

$500
$1400
$100
NO SHIPMENT POSSIBLE
$2600

DATA SET  2 (there are two spaces after the word SET)

NO SHIPMENT POSSIBLE

END OF OUTPUT

Code: Select all

2
1 0 0
AA
1 0 0
AA

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1


DATA SET  2


END OF OUTPUT

Code: Select all

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

class Node
{
  public:
            Node(){}
            char color;
            int d;
};

class Queue
{
  public:
            Queue(int n)
            {
                Q = new int[n];
                len = 0;
            }
            int len;
            int* Q;
            void Enq(int m)
            {
                Q[len] = m;
                len++;
            }
            int Deq()
            {
                len--;
                return Q[len];
            }
            bool IsEmpty()
            {
                if(len == 0)
                    return true;
                return false;
            }

};

void BFS(int s,Node* node,int** adjWh,int n)
{
    for(int i=0;i<n;i++)
    {
        node[i].color = 'W';
        node[i].d = -1;
    }
    node[s].color = 'G';
    node[s].d = 0;
    Queue Q(n);
    Q.Enq(s);
    while(Q.IsEmpty() == false)
    {
        int u = Q.Deq();
        for(int v=0;v<n;v++)
        {
            if(adjWh[u][v] == 1 && node[v].color == 'W')
            {
                node[v].color = 'G';
                node[v].d = node[u].d + 1;
                Q.Enq(v);
            }
        }
        node[u].color = 'B';
    }
}


int main()
{
    cout<<"SHIPPING ROUTES OUTPUT\n\n";
    int a[26][26]={0};
    int n;
    cin>>n;
    int c = n+1;
    while(n>0)
    {
        printf("DATA SET  %d\n\n",c-n);
        n--;
        int w,l,r;
        cin>>w>>l>>r;
        int** adjWh = new int*[w];
        for(int i=0;i<w;i++)
            adjWh[i] = new int[w];
        for(int i=0;i<w;i++)
            for(int j=0;j<w;j++)
                adjWh[i][j] = 0;
        string inWh;
        for(int i=0;i<w;i++)
        {
            cin>>inWh;
            a[inWh[0] - 'A'][inWh[1] - 'A'] = i;
        }
        string legL,legR;
        for(int i=0;i<l;i++)
        {
            cin>>legL>>legR;
            adjWh[a[legL[0] - 'A'][legL[1] - 'A']][a[legR[0] - 'A'][legR[1] - 'A']] = 1;
            adjWh[a[legR[0] - 'A'][legR[1] - 'A']][a[legL[0] - 'A'][legL[1] - 'A']] = 1;
        }
        Node* node = new Node[w];

        int** bfsDis = new int*[w];
        for(int i=0;i<w;i++)
        {
            bfsDis[i] = new int[w];
        }

        for(int i=0;i<w;i++)
        {
            BFS(i,node,adjWh,w);
            for(int j=0;j<w;j++)
                bfsDis[i][j] = node[j].d;
        }
        int rWeight,rNumberOfLegs;
        string rWhL,rWhR;
        for(int i=0;i<r;i++)
        {
            cin>>rWeight>>rWhL>>rWhR;
            rNumberOfLegs = bfsDis[a[rWhL[0] - 'A'][rWhL[1] - 'A']][a[rWhR[0] - 'A'][rWhR[1] - 'A']];
            if(rNumberOfLegs >= 0)
            {
                cout<<"$"<<(rWeight*rNumberOfLegs*100)<<endl;
            }
            else
                cout<<"NO SHIPMENT POSSIBLE"<<endl;
        }
        cout<<endl;

    }
    cout<<"END OF OUTPUT";

    return 0;
}