## 10000 - Longest Paths

Moderator: Board moderators

Ioura
New poster
Posts: 1
Joined: Tue Mar 12, 2002 2:00 am
Contact:

### 10000 - Longest Paths

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

It is a small bug...
Just increase your table from 5000x2 to
10010x2

And you will get it...

Good Luck

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

### 10000

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

}

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
it work on my computer, but doesn't work on serwer:((
what could be wrong?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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++.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
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;

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
so what should i do?? to correct this proglem, it gives wrong answer on serwer, but it's working on my computer

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
this line should be
if ((L > maxl) || (( L == maxl) && (start < end )) )
but it doesn't work still

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
Are the points numbered from 1 to n?

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
from 0 to n-1

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Are you sure? The problem description says "1 to n", and I can't see where you decrease the numbers by one.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
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;
}
}

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
#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>