## 10000 - Longest Paths

Moderator: Board moderators

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
I got AC with the floyd warshall's algorithm ..... It was so simple ... I don't know whats wrong with ma dfs algorithm ....

leeyeanhoo
New poster
Posts: 4
Joined: Sat Nov 04, 2006 5:40 am

### hi ! please show me how did you correct the program

Hi

Im very fresher in this kind of problem and im looking for how I could solve this problem

Regards

caojun
New poster
Posts: 1
Joined: Mon Dec 11, 2006 9:36 am

### 10000 WA. Memory Limit Exceeded!

I've tried every means,and I still got "Memory Limit Exceeded",can anybody help me,please? Thank you.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

struct Edge {
unsigned short int num;
struct Edge *next;
};

struct IN {
unsigned short int n;
int start;
struct Edge **edges;
};

struct node {
unsigned short int num;
unsigned short int depth;
struct node* next;
};

struct result { /* to store the results*/
unsigned short int start;
unsigned short int len;
unsigned short int end;
struct result* next;
};

void freeNode(struct IN *in) {
struct Edge *pt, *et;
unsigned short int i;

for (i = 0; i < in->n; i++) {
pt = (in->edges)[i];
while (pt != NULL) {
et = pt->next;
free(pt);
pt = et;
}
}
free(in->edges);
free(in);
}

void push(struct node **qHead, struct node **qTail, int num, int depth) {
struct node *pt;
pt = malloc(sizeof(struct node));
pt->num = num;
pt->depth = depth;
pt->next = NULL;

*qTail = pt;
return;
}
(*qTail)->next = pt;
*qTail = pt;
}

struct node* pop(struct node **qHead) {
struct node *pt;
return NULL;
return pt;
}

void process(unsigned short int *len, unsigned short int *end, struct IN *in) {
struct Edge *edge;
struct result *rt;
unsigned short int flag;

rt = malloc(sizeof(struct result));
rt->start = in->start;
qTail = NULL;
push(&qHead, &qTail, in->start - 1, 0);
*len = 0;
*end = in->n;

flag = 1;
for (edge = (in->edges)[current->num]; edge != NULL; edge = edge->next) {
push(&qHead, &qTail, edge->num, current->depth + 1);
flag = 0;
}
if (flag)
if (current->depth > *len) {
*len = current->depth;
*end = current->num;
} else
if (current->depth == *len && current->num < *end)
*end = current->num;
free(current);
}
}

int main() {
struct IN *in;
struct Edge *edge;
int i, j;

while (1) {
in = malloc(sizeof(struct IN));
scanf("%i", &(in->n));
if (in->n == 0)
break;

in->edges = malloc(sizeof(struct Edge*) * (in->n));
for (i = 0; i < in->n; i++)
(in->edges)[i] = NULL;
scanf("%i", &(in->start));

while (1) {
scanf("%i %i", &i, &j);
if (i == 0 && j == 0) { //process this graph and store the result
process(&(rt->len), &(rt->end), in);
rt->start = in->start;
rt->next = malloc(sizeof(struct result));
rt = rt->next;
freeNode(in);
break;
}
if ((in->edges)[i - 1] == NULL) {
(in->edges)[i - 1] = malloc(sizeof(struct Edge));
((in->edges)[i - 1])->next = NULL;
((in->edges)[i - 1])->num = j - 1;
} else {
for (edge = (in->edges)[i - 1]; edge->next != NULL; edge = edge->next)
;
edge->next = malloc(sizeof(struct Edge));
edge = edge->next;
edge->num = j - 1;
edge->next = NULL;
}
/*printf("(in->edges)[%i]->num == %i\n", i - 1, j - 1);*/
}
}

/*output the results*/
for (rt = rtHead, i = 0; rt->next != NULL;) {
printf("Case %i: The longest path from %i has length %i, finishing at %i.\n",
++i, rt->start, rt->len, rt->end + 1);
rtTemp = rt->next;
free(rt);
rt = rtTemp;
}
free(rt);
return 0;
}

``````

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
doesnt floyd warshall algorithm find out the shortest path b/w vertices.in this problem we are supposed to find longest path. how can we use floyd warshall algorithm ??

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

### keeping WA

keeping WA (pass all the test cases which i could find on the board)
any idea???

Code: Select all

``````Remove after AC, the following test cases are valid.

``````
Input:

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 4
5 3
5 2
5 1
4 1
4 2
0 0
8
1
7 1
8 1
1 3
2 3
4 3
3 5
6 2
0 0
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
2
1
1 2
0 0
10
6
1 2
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 10
7 2
2 8
0 0
2
1
0 0
2
2
0 0
2
2
1 2
0 0
2
1
1 2
0 0
2
1
2 1
0 0
2
2
2 1
0 0
7
1
1 2
1 4
2 7
2 5
4 3
4 6
2 4
3 6
3 7
0 0
0
``````
Output:

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 2, finishing at 5.

Case 5: The longest path from 1 has length 5, finishing at 6.

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

Case 7: The longest path from 6 has length 5, finishing at 10.

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

Case 9: The longest path from 2 has length 0, finishing at 2.

Case 10: The longest path from 2 has length 0, finishing at 2.

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

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

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

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

``````
Last edited by sjn on Fri Apr 20, 2007 3:16 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Some of your cases are not correct I think. However, here are some cases where your code fails.

Input:

Code: Select all

``````6
6
6 5
1 4
6 4
5 1
6 1
5 3
5 4
6 2
4 2
0 0
13
11
11 6
13 11
9 1
7 11
4 11
1 12
12 10
12 8
6 9
11 10
6 10
11 8
6 1
5 13
2 13
0 0
0``````
Output:

Code: Select all

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

Case 2: The longest path from 11 has length 5, finishing at 8.``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:
Jan wrote:Some of your cases are not correct I think. However, here are some cases where your code fails.
...
Hope these help.
Thank you very much, JAN!

my problem is that i forgot to add 1 when i prune the part of recalculation.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
I got WA for this problem

Code: Select all

``AC``
I tried many cases and it produces correct output. Does anyone have critical test cases ?
Last edited by RC's on Wed Aug 15, 2007 6:08 am, edited 1 time in total.

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
I try to use BFS, but I got WA. Can anyone help me?

Code: Select all

``````AC
``````
Thank you.
Last edited by renato_ferreira on Tue Aug 14, 2007 1:11 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your code is correct, but way to slow. Just generate a set which has 100 nodes and all possible edges. The starting node is 1.

Input:

Code: Select all

``````100
1
1 2
1 3
1 4
.
.
.
1 100
2 3
2 4
2 5
.
.
.
2 100
3 4
.
.
.
99 100
0 0
0``````
Output:

Code: Select all

``Case 1: The longest path from 1 has length 99, finishing at 100.``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
But I got WA, no TLE...

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I just submitted your code and got TLE.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
I changed my code, but got WA in 0.189.

Code: Select all

``````AC
``````
Thank you.
Last edited by renato_ferreira on Tue Aug 14, 2007 1:11 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your current code fails for some cases. Check the I/O files.

Input
Output

Hope these help.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
I can change the code to work for the inputs, but I get TLE. How can I optimize this code?

Code: Select all

``````AC
``````
Thank you.
Last edited by renato_ferreira on Tue Aug 14, 2007 1:10 am, edited 1 time in total.