10000 - Longest Paths
Moderator: Board moderators
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
very complex implementation of BFS indeed.
you have used adjacency list.
while(v && e)
{
j=0;
while(p[v].paths[j]>=0)j++;
p[v].paths[j]=e;
scanf("%d %d",&v,&e);
}
for the colored part you can use another counter array.it will reduce the time.
set max=-1;
for(j=0;j<=N;j++)
{
if(p[j].dis>max)
{
max=p[j].dis;
end=j;
}
}
why j=0,don't know.
no need of the condition , atleast for this program
if(counter>p[p[q].paths[j]].dis)
so u can remove it.
by the way the matrix method implementation is easier for this program.
you have used adjacency list.
while(v && e)
{
j=0;
while(p[v].paths[j]>=0)j++;
p[v].paths[j]=e;
scanf("%d %d",&v,&e);
}
for the colored part you can use another counter array.it will reduce the time.
set max=-1;
for(j=0;j<=N;j++)
{
if(p[j].dis>max)
{
max=p[j].dis;
end=j;
}
}
why j=0,don't know.
no need of the condition , atleast for this program
if(counter>p[p[q].paths[j]].dis)
so u can remove it.
by the way the matrix method implementation is easier for this program.
cuii e
- Ali Arman Tamal
- Learning poster
- Posts: 76
- Joined: Sat Jan 15, 2005 5:04 pm
- Location: Dhaka
- Contact:
10000 Why TLE ??
I'm getting TLE
don't know why...
Here is my code
The problem description says
THANKS FOR READING !!
[/quote]
![:cry:](./images/smilies/icon_cry.gif)
Here is my code
Code: Select all
#include <stdio.h>
int a[101][101],parent[101],d[101];
int n,root,casecount=0;
void process(int k);
void findpath();
int main()
{
int i,j;
while(1)
{
scanf("%d",&n);
if(n==0)break;
casecount++;
for(i=1;i<=n;i++)
{
parent[i]=-1;
d[i]=0;
for(j=1;j<=n;j++)a[i][j]=0;
}
scanf("%d",&root);
parent[root]=-1;
while(1)
{
scanf("%d %d",&i,&j);
if(i==0 && j==0)break;
a[i][j]=1;
}
process(root);
findpath();
}
return 1;
}
void process(int k)
{
int i=1;
while(i<=n)
{
if(a[k][i]==1)if(d[k]+1>d[i]){ d[i]=d[k]+1; parent[i]=k; }
i++;
}
i=1;
while(i<=n){ if(a[k][i]==1)process(i); i++; }
}
void findpath()
{
int k,max=root,count;
for(k=1;k<=n;k++)
{
if(d[k]>d[max])max=k;
else if(d[k]==d[max] && k<max)max=k;
}
count=0;
if(max!=root){
k=max;
while(parent[k]!=-1){ k=parent[k]; count++; }
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",casecount,root,count,max);
}
My code will certainly give TLE if the graph is cyclic, but I'm not sure if it is the reason.You can assume that the graph has no cycles (there is no path from any node to itself),
![:o](./images/smilies/icon_eek.gif)
THANKS FOR READING !!
![:)](./images/smilies/icon_smile.gif)
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
- Ali Arman Tamal
- Learning poster
- Posts: 76
- Joined: Sat Jan 15, 2005 5:04 pm
- Location: Dhaka
- Contact:
10000, help me to understand the meaning of "p,q"
Does the pair of p and q means:
1.There is a path from p to q. And there may be some other nodes between p and q. For example, it can be p->1->2->q
Or
2.There is a edge from p to q in the graph. That is p->q, no other nodes between them.
Which of the two understanding is right?
1.There is a path from p to q. And there may be some other nodes between p and q. For example, it can be p->1->2->q
Or
2.There is a edge from p to q in the graph. That is p->q, no other nodes between them.
Which of the two understanding is right?
I stay home. Don't call me out.
Re: 10000, help me to understand the meaning of "p,q&qu
The latter will do...ImLazy wrote:Does the pair of p and q means:
1.There is a path from p to q. And there may be some other nodes between p and q. For example, it can be p->1->2->q
Or
2.There is a edge from p to q in the graph. That is p->q, no other nodes between them.
Which of the two understanding is right?
Ciao!!!
Claudio
10000 WA
Cant find the problem... I'm always getting WA...
Code: Select all
const maxn = 100;
var a : array [0..maxn,0..maxn] of integer;
q,l : array [0..maxn*maxn] of integer;
c,n,i,x,y,st,max,maxi,t,j,yk,yp,cur : integer;
w : array [0..maxn+1,0..maxn+1] of boolean;
h : boolean;
begin
{ assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
}
n:=1;
c:=0;
while n<>0 do
begin
readln(n);
if n>0 then
begin
{}
readln(st);
fillchar(a,sizeof(a),0);
x:=1; y:=1;
while not((x=0)and(y=0)) do
begin
readln(x,y);
if not((x=0)and(y=0)) then
begin
inc(a[x,0]);
a[x,a[x,0]]:=y;
end;
end;
{}
max:=0; maxi:=st;
yk:=1; yp:=1; q[yk]:=st; l[yk]:=0;
while yk<=yp do
begin
cur:=q[yk];
for i:=1 to a[cur,0] do
begin
if w[a[cur,i],l[yk]+1]=false then
begin
w[a[cur,i],l[yk]+1]:=true;
inc(yp);
q[yp]:=a[cur,i];
l[yp]:=l[yk]+1;
end;
end;
if (l[yk]>max)or((l[yk]=max)and(q[yk]<maxi)) then
begin
max:=l[yk];
maxi:=q[yk];
end;
inc(yk);
end;
{}
inc(c);
writeln('Case ',c,': The longest path from ',st,' has length ',max,', finishing at ',maxi,'.');
writeln;
{}
end;
end;
{ close(input); close(output);}
end.
I tested it on:
And it produced:
The output should be:
... since input data for Case 1 and Case 2 is the same.
Try initializing the w[][] variable before anything else is done.
Code: Select all
2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
2
1
1 2
0 0
0
Code: Select all
Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.
Case 4: The longest path from 1 has length 0, finishing at 1.
Code: Select all
Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.
Case 4: The longest path from 1 has length 1, finishing at 2.
![:)](./images/smilies/icon_smile.gif)
Try initializing the w[][] variable before anything else is done.
![:wink:](./images/smilies/icon_wink.gif)
Code: Select all
for i := 0 to maxn+1 do
for j := 0 to maxn+1 do
w[i][j] := false;
10000 Longest Paths - TLE
hi all...
I solved this problem(10000-longest paths) using back-tracking algorithm technic...
it gave me correct answers for the sample input..
but.. judger replied the code was TLE...
it is so fool of me...
how do I speed up using back-tracking algorithm technic ??
and would you give me a sample test case which occurs TLE ??
thanks in advance...
ps.. sorry for poor english... excuse me![:)](./images/smilies/icon_smile.gif)
I solved this problem(10000-longest paths) using back-tracking algorithm technic...
it gave me correct answers for the sample input..
but.. judger replied the code was TLE...
it is so fool of me...
![:cry:](./images/smilies/icon_cry.gif)
how do I speed up using back-tracking algorithm technic ??
and would you give me a sample test case which occurs TLE ??
thanks in advance...
ps.. sorry for poor english... excuse me
![:)](./images/smilies/icon_smile.gif)
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
-
- Learning poster
- Posts: 83
- Joined: Wed Feb 01, 2006 12:59 pm
- Location: (Fci-cu) Egypt
- Contact:
Salamo Aleko
As for ur code u need to prune ur search as guided above........
But you also can solve this problem easily by using floyd warshal algorithm to find shortest path...
Only you need to minor changes
To make it find the longest path
Using bfs or dfs I got ac in 0.387s
Using floyd I got ac in 1.275
http://acm.uva.es/problemset/usersjudge.php?user=8957CA
As for ur code u need to prune ur search as guided above........
But you also can solve this problem easily by using floyd warshal algorithm to find shortest path...
![:P](./images/smilies/icon_razz.gif)
To make it find the longest path
Using bfs or dfs I got ac in 0.387s
Using floyd I got ac in 1.275
http://acm.uva.es/problemset/usersjudge.php?user=8957CA
10000 `algo
Is my algo wrong??
I am getting wrong answer,
Can anyone help me ?
Code: Select all
/*
* 10000 longest path
* submission 1 WA
* coded at 1157am , may 11, 2006
*/
#include <cstdio>
#include <queue>
#define max(a,b) (((a)>(b)) ? (a):(b))
using namespace std;
int main() {
struct {
int edge[100];
int nedge;
int dist;
bool processed;
bool discovered;
}node[101];
int n,s,i,j,a,b,cur,max,end,cases=0;
int cedge;
queue<int> Q;
while(scanf("%d",&n)==1 && n) {
scanf("%d",&s);
//init
for(i=1;i<=n;i++) {
node[i].nedge=0;
node[i].dist=0;
node[i].processed=node[i].discovered=false;
}
//input
while(true) {
scanf("%d%d",&a,&b);
if(a==0 && b==0) break;
node[a].edge[node[a].nedge++]=b;
}
//bfs
Q.push(s);
while(!Q.empty()) {
cur=Q.front();
Q.pop();
for(i=0;i<node[cur].nedge;i++) {
cedge=node[cur].edge[i];
node[cedge].dist=max(node[cedge].dist,node[cur].dist+1);
if(node[cedge].processed) continue;
if(!node[cedge].discovered) {
node[cedge].discovered=true;
Q.push(cedge);
}
}
node[cur].processed=true;
}
//finding max
max=0;
for(i=1;i<=n;i++) {
if(node[i].dist>max) {
max=node[i].dist;
end=i;
}
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",++cases,s,max,end);
}
return 0;
}
![:o](./images/smilies/icon_eek.gif)
Can anyone help me ?
fahim
#include <smile.h>
#include <smile.h>