Page **1** of **11**

### 10000 - Longest Paths

Posted: **Tue Mar 12, 2002 10:54 pm**

by **Ioura**

This code seems to work whatever I feed it with but I still get WA. Can someone help ?

Code: Select all

```
#include <stdio.h>
int edge[5000][2];
int node[101];
int nodes;
int edges, length;
int main()
{
int start, i, j, ncase, cont;
for(scanf("%d",&nodes),ncase=1; nodes>0; scanf("%d",&nodes),ncase++) {
scanf("%d",&start);
edges=-1;
do {
edges++;
scanf("%d %d",&edge[edges][0],&edge[edges][1]);
} while (edge[edges][0] != 0 && edge[edges][1] != 0);
for(i=1; i<=nodes; i++) node[i]=-1;
node[start]=0;
length=-1;
do {
cont=0;
length++;
for (i=1; i<=nodes; i++)
if (node[i]==length)
for (j=0;j<edges;j++)
if (edge[j][0]==i) {
node[edge[j][1]]=length+1;
cont=1;
}
} while (cont);
for (i=1;node[i]<length;i++);
printf("Case %d: The longest path from %d has length %d, finishing at %d.nn",ncase,start,length,i);
}
return 0;
}
```

Posted: **Mon Mar 18, 2002 1:29 pm**

by **cyfra**

Hi!

It is a small bug...

Just increase your table from 5000x2 to

10010x2

And you will get it...

Good Luck

### 10000

Posted: **Tue Mar 19, 2002 10:44 pm**

by **PMNOX**

#include <iostream.h>

#include <math.h>

struct record

{

record *right;

int y;

};

void calc(record *B[],int start, int &maxl,int &end, int L)

{

if ((L > maxl) || (( L = maxl) && (L > end )) )

{

maxl = L;

end = start;

}

record *q=B[start];

while(q != NULL)

{

calc(B,q->y,maxl,end,L+1);

q = q -> right;

}

}

void delet(record *B[],int number)

{

record *p=B[number],*q;

for(int i = 0; i < number;i++)

{

while(p!= NULL)

{

q = p;

p = p -> right;

delete(q);

}

}

}

void max(record *B[],int x,int y)

{

if(B[x-1] != NULL)

{

record *q = B[x - 1];

while(q-> right != NULL)

{

q = q -> right;

}

record *p = new(record);

q -> right = p;

p -> right = NULL;

p -> y = y - 1;

}

else

{

B[x-1] = new(record);

B[x-1] -> y = y-1;

B[x-1] -> right = NULL;

}

}

void procedure(int number,int cas)

{

int start,maxl=0,end=0;

cin>>start;

start--;

int A[101][2];

int j=0;

cin>>A[j][0];

while(A[j][0] != 0) //read table a

{

cin>>A[j][1];

j++;

cin>>A[j][0];

}

cin>>A[j][1];

record* B[101];

for(int i = 0; i< number;i++)

{

B* = NULL;*

}

int c = 0;

while(A[c][0] != 0)

{

max(B,A[c][0],A[c][1]); // convert from table a to table b

c++;

}

calc(B,start,maxl,end,0); //calculate distacre

cout<<"Case "<<cas<<": The longest path from "<<start+1<<" has length "<<maxl<<", finishing at "<<end + 1<<"."<<endl;

for(int d=0;d<number;d++)

delet(B,d);//delete array from memory

}

void main()

{

int cas=1;

int number;

cin>>number;

while(number != 0)

{

procedure(number,cas);

cin>>number;

cas++;

}

}

Posted: **Tue Mar 19, 2002 10:45 pm**

by **PMNOX**

it work on my computer, but doesn't work on serwer:((

what could be wrong?

Posted: **Tue Mar 19, 2002 11:18 pm**

by **Adrian Kuegel**

I remember I had a problem with the long line in the output. I splitted it in two parts and got accepted. But I don't know if it is necessary in C++.

Posted: **Wed Mar 20, 2002 2:35 am**

by **PMNOX**

i tried this way

cout<<"Case ";

cout<<endl;

cout<<cas;

cout<<endl;

cout<<": The longest path from ";

cout<<endl;

cout<<start+1;

cout<<endl;

cout<<" has length ";

cout<<endl;

cout<<maxl;

cout<<endl;

cout<<", finishing at ";

cout<<endl;

cout<<end + 1;

cout<<endl;

cout<<".";

cout<<endl;

and this way, it doesn't work still;

cout<<"Case ";

cout<<cas;

cout<<": The longest path from ";

cout<<start+1;

cout<<" has length ";

cout<<maxl;

cout<<", finishing at ";

cout<<end + 1;

cout<<".";

cout<<endl;

Posted: **Wed Mar 20, 2002 2:49 am**

by **Stefan Pochmann**

Adrian, it's not necessary for C++ to split the line. I'm not sure if there's a limit, but it's definitely way higher than that line. The problem probably was that your mail program splitted the line because it thought it's too long and it splitted it on a wrong position.

Posted: **Wed Mar 20, 2002 10:24 am**

by **PMNOX**

so what should i do?? to correct this proglem, it gives wrong answer on serwer, but it's working on my computer

Posted: **Wed Mar 20, 2002 10:49 am**

by **Adrian Kuegel**

I think you have made a mistake in procedure calc:

if ((L > maxl) || (( L = maxl) && (L > end )) )

I think you must write L==maxl.

And have you considered this line:

If there are several paths of maximum length, print the final place with smallest number.

Posted: **Wed Mar 20, 2002 4:36 pm**

by **PMNOX**

this line should be

if ((L > maxl) || (( L == maxl) && (start < end )) )

but it doesn't work still

Posted: **Thu Mar 21, 2002 1:35 pm**

by **junjieliang**

Are the points numbered from 1 to n?

Posted: **Fri Mar 22, 2002 4:54 pm**

by **PMNOX**

from 0 to n-1

Posted: **Sat Mar 23, 2002 2:58 am**

by **Stefan Pochmann**

Are you sure? The problem description says "1 to n", and I can't see where you decrease the numbers by one.

Posted: **Sat Mar 23, 2002 9:43 am**

by **PMNOX**

i do it here void

max(record *B[],int x,int y)

{

if(B[x-1] != NULL)

{

record *q = B[x - 1];

while(q-> right != NULL)

{

q = q -> right;

}

record *p = new(record);

q -> right = p;

p -> right = NULL;

p -> y = y - 1;

}

else

{

B[x-1] = new(record);

B[x-1] -> y = y-1;

B[x-1] -> right = NULL;

}

}

Posted: **Sat Mar 23, 2002 10:01 am**

by **PMNOX**

#include <iostream.h>

#include <math.h>

struct record

{

record *right;

int y;

};

void calc(record *B[],int start, int &maxl,int &end, int L)

{

if ((L > maxl) || (( L == maxl) && (start < end )) )

{

maxl = L;

end = start;

}

record *q=B[start];

while(q != NULL)

{

calc(B,q->y,maxl,end,L+1);

q = q -> right;

}

}

void delet(record *B[],int number)

{

record *p,*q;

for(int i = 0; i < number;i++)

{

p = B*;*

while(p != NULL)

{

q = p;

p = p -> right;

delete(q);

}

}

}

void max(record *B[],int x,int y)

{

if(B[x] != NULL)

{

record *q = B[x];

while(q-> right != NULL)

{

q = q -> right;

}

q -> right = new(record);

q = q -> right;

q -> right = NULL;

q -> y = y;

}

else

{

B[x] = new(record);

B[x] -> y = y;

B[x] -> right = NULL;

}

}

void procedure(int number,int cas)

{

int start,maxl=-1,end=-1;

cin>>start;

start--;

int A[101][2];

int j=-1;

do

{

j++;

cin>>A[j][0];

cin>>A[j][1];

}

while((A[j][0] != 0) && (A[j][1] != 0));

record* B[101];

for(int i = 0; i<= number;i++)

{

B* = NULL;*

}

int c = 0;

while(A[c][0] != 0)

{

max(B,A[c][0]-1,A[c][1]-1); // convert from table a to table b

c++;

}

calc(B,start,maxl,end,0); //calculate distacre

cout<<"Case "<<cas<<": The longest path from "<<start+1<<" has length "<<maxl<<", finishing at "<<end + 1<<"."<<endl;

// for(int d=0;d<number;d++)

// delet(B,d);//delete array from memory

}

void main()

{

int cas=1;

int number;

cin>>number;

while(number != 0)

{

procedure(number,cas);

cin>>number;

cas++;

}

}

<font size=-1>[ This Message was edited by: PMNOX on 2002-03-23 09:02 ]</font>

<font size=-1>[ This Message was edited by: PMNOX on 2002-03-23 12:38 ]</font>