383 - Shipping Routes

[sahand]

There should be an 'Edit' button right next to your post.
Take care...

[Lord Nemrod]

Thanks a lot~!

[HomemPalindromo]

I'm getting a WA too, I guess I don't handle empty (zero) requests the correct way.

What is the correct output for this input ?

Code: Select all

1
1 0 0
AA

Is it this:

Code: Select all

SHIPPING ROUTES OUTPUT

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

Or this ?

Code: Select all

SHIPPING ROUTES OUTPUT

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

[sahand]

Hey,
My AC program outputs

Code: Select all

SHIPPING ROUTES OUTPUT

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

But if you're getting WA instead of PE (Presentation Error) you should consider checking your algorithm instead.

Good luck,
Sahand.

[Carunty]

I dont know why I get PE.
Anyone have an idea?

Here is my code.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int main(){
int n; cin >> n; cout << "SHIPPING ROUTES OUTPUT" << endl;
for(int i=1;i<=n;++i){
cout << endl << "DATA SET "; if(i<10) cout <<" "; cout << i << endl << endl;
int t=0,x,y,z; cin >> x >> y >> z; string h,k; vector<vector<string> > v; map<string,int> m;
for(int j=0;j<x;++j){cin>>h; m[h]=j; vector<string> w; v.push_back(w);}
for(int j=0;j<y;++j){cin >> h >> k; v[m[h]].push_back(k); v[m[k]].push_back(h);}
for(int j=0;j<z;++j){
cin >> y >> h >> k; int a[x]; memset(a,0,sizeof(a)); a[m[h]]=1; queue<string> q; q.push(h);
while(!q.empty()){
string s=q.front(),t;
for(int i=0;i<v[m[s]].size();++i){
t=v[m[s]];
if(a[m[t]]==0){
a[m[t]]=a[m[s]]+1; q.push(t);
if(t==k) break;
}
}
if(t==k) break; q.pop();
}
if(a[m[k]]>0) cout<<"$"<<(a[m[k]]-1)*100*y<<endl; else cout<<"NO SHIPMENT POSSIBLE"<<endl;
}
}
cout << endl << "END OF OUTPUT";
}

[Carunty]

Anyone can help me?

[turcse143]

hi sahand
may be u r wrong.
because my AC code shows

Code: Select all

SHIPPING ROUTES OUTPUT

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

this is correct

[regan]

#include<iostream>
#include<queue>
#include<vector>
#define max 50

using namespace std;

vector <long> edge[max];
char node[max][10];
long color[max],dist[max],n;

long find_pos(char *name)
{
long pos=-1;
for(long i=0;i<=n;i++)
{
if(strcmp(name,node)==0)
{
pos=i;
break;
}
}
if(pos==-1)
{
pos=n;
n++;
strcpy(node[pos],name);
}
return pos;
}

void bfs(long source,long n)
{
long u,i;
for(i=0;i<n;i++)
{
color=1;
dist=10000;
}
color[source]=2;
queue <long> q;
dist[source]=0;
q.push(source);
while(!q.empty())
{
u=q.front();
q.pop();
for(i=0;i<edge.size();i++)
{
if(color[edge]==1)
{
color[edge]=2;
dist[edge]=dist+1;
q.push(edge);
}
}
}
}

int main()
{
long t,l,j,k,n,m,q,ship;
char nam[10],namm[10],ch;
cin>>t;
cout<<"SHIPPING ROUTES OUTPUT\n\n";
for(l=0;l<t;l++)
{
cout<<"DATA SET "<<l+1<<endl<<endl;
cin>>n>>m>>q;
for(j=0;j<n;j++) {
scanf("%s",&nam);
find_pos(nam);
}
for(j=0;j<m;j++)
{
cin>>nam>>namm;
edge[find_pos(nam)].push_back(find_pos(namm));
edge[find_pos(namm)].push_back(find_pos(nam));
}
for(j=0;j<q;j++)
{
scanf("%ld%c%s%s",&ship,&ch,&nam,&namm);
bfs(find_pos(nam),n);
if(dist[find_pos(namm)]==10000)
{
cout<<"NO SHIPMENT POSSIBLE\n";
}
else
{
cout<<"$"<<ship*100*dist[find_pos(namm)]<<endl;
}
}
cout<<endl;
for(j=0;j<n;j++) edge[j].clear();
}
cout<<"END OF OUTPUT\n";
return 0;
}

[AnindyaPaul]

This is the output format of my AC code.

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" );

Notice the format specifier for DATA SET. It should be %2d.

[vsha041]

For those of you getting presentation errors notice that after DATA SET you need to print two spaces. See below:

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

Apart from that there are no tricks in this question. Here is one another test case:

Input

Code: Select all

2
1 0 0
AA
1 0 0
AA

Output

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1


DATA SET  2


END OF OUTPUT

Notice that there are two blank lines after data set 1 and 2. Your program should handle that by default.

[sidsi]

thnx vsha041 i don't think i could figure the two spaces...

[Pooria]

I used BFS and still getting WA.
Can anyone help me with this pls

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;
}

[brianfry713]

Always print a newline char at the end of the last line.