10000 - Longest Paths

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

10000: Longest Path - Why is Time Limit Exceeded ?

Post by joeluchoa »

Code: Select all

I've got AC now! 
Last edited by joeluchoa on Wed Aug 16, 2006 3:44 pm, edited 2 times in total.

nahidshahin
New poster
Posts: 8
Joined: Mon Nov 10, 2003 10:54 am
Location: Bangladesh
Contact:

10000

Post by nahidshahin »

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

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish »

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

[cpp]
got AC using bfs ...
[/cpp]
if u can think of it .. u can do it in software.

JuaingFall
New poster
Posts: 13
Joined: Tue Aug 03, 2004 4:24 am
Location: CHINA

Post by JuaingFall »

I use neither of them :P

JuaingFall
New poster
Posts: 13
Joined: Tue Aug 03, 2004 4:24 am
Location: CHINA

Post by JuaingFall »

you should try to change another method to solve this problem :oops:

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics »

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

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Need I/O-10000

Post by Zuberul »

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

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by 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. :)
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by 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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by 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
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul »

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

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by 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
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul »

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

Post Reply

Return to “Volume 100 (10000-10099)”