10000 - Longest Paths

[joeluchoa]

Code: Select all

I've got AC now! 

[nahidshahin]

why DFS not work here.
But BFS working
I get AC using BFS

[jagadish]

i get WA by using floyds''s can anyone help me out..

[cpp]
got AC using bfs ...
[/cpp]

[JuaingFall]

I use neither of them

[JuaingFall]

you should try to change another method to solve this problem

[alu_mathics]

Try to use bfs or floyd warshall.
I think bfs will be better.

[Zuberul]

I used bfs & got WA
someone please give me some I/O.
Is there any tricky cases?

[Niaz]

It is not true that DFS is not working here. I have solved this problem at first (before re-judging) with DFS. But After re-judging I got TLE and then I have attacked this problem with BFS and at that time I got WA. Finally I have managed to solve this `funny' problem with DFS with some pruning. I got the hint from Steven's page and that's why LATE THANKS to Steven.

[Zuberul]

I also tried DFS earlier but managed to get a WA.
and again WA with BFS.
I cant find out what i am missing.
give me some input cases.

[Antonio Ocampo]

Try this

Input

4
3
1 2
4 3
0 0
0


Output

Case 1: The longest path from 3 has length 0, finishing at 3.

[Zuberul]

My code gives the same output.
Then what might be the problem.
please give me more I/O

[Ghust_omega]

Hi !! Zuberul try with this
In :

Code: Select all

5
1
1 2
1 3
3 4
2 5
0 0
0

out :

Code: Select all

Case 1: The longest path from 1 has length 2, finishing at 4.

Hope it Helps
Keep posting !!

[Zuberul]

My code pass this one also.
So i am now posting my code.

#include<stdio.h>

#define SIZE 110

typedef struct{
int paths[SIZE];
int dis;
}vertex;

vertex p[SIZE];

int max,end,start,que[SIZE],size,head,tail;


void addque(int a)
{
que[tail]=a;
size++;
tail=((tail+1)%SIZE);
}


int getque()
{
int temp;
size--;
temp=que[head];
head=((head+1)%SIZE);
return temp;
}
void BFS(int i)
{
int j=0,q=0,counter=1;

addque(i);
while(size!=0)
{
q=getque();
counter=p[q].dis+1;
j=0;
while(p[q].paths[j]>-1)
{
if(counter>p[p[q].paths[j]].dis)
{
p[p[q].paths[j]].dis=counter;
addque(p[q].paths[j]);
}
j++;
}
}
}

void doBFS(int N)
{
int j;
BFS(start);
for(j=0;j<=N;j++)
{
if(p[j].dis>max)
{
max=p[j].dis;
end=j;
}
}
if(max==0)end=start;
printf("The longest path from %d has length %d",start,max);
printf(", finishing at %d.\n",end);
}

void main()
{
int N,num,i,v,e,j,no=0;

/*freopen("d:\\in10000.txt","r",stdin);*/
scanf("%d",&N);

while(N!=0)
{
no++;
scanf("%d",&start);
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
p[i].paths[j]=-1;
}
p[i].dis=0;
que[i]=-1;
}
scanf("%d %d",&v,&e);
while(v && e)
{
j=0;
while(p[v].paths[j]>=0)j++;
p[v].paths[j]=e;
scanf("%d %d",&v,&e);
}
max=0;
end=-1;
size=head=tail=0;
printf("Case %d: ",no);
doBFS(N);
scanf("%d",&N);
printf("\n");
}
}[/quote]

[Ghust_omega]

Hi !! Zeberul I got AC with Warshal algo I read in another thread that BFS causes WA and DFS causes TLE
Hope it helps
Keep posting

[Zuberul]

yep man I got AC with Floyd Warshall at last.
But i still cant imagine why bfs fails here.
Thanks for the help.