10000 - Longest Paths

[sakhassan]

I got AC with the floyd warshall's algorithm ..... It was so simple ... I don't know whats wrong with ma dfs algorithm ....

[leeyeanhoo]

Hi

Im very fresher in this kind of problem and im looking for how I could solve this problem
Please could you post what was wrong with your code?


Regards

[caojun]

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;

	if (*qHead == NULL) {
		*qHead = pt;
		*qTail = pt;
		return;
	}
	(*qTail)->next = pt;
	*qTail = pt;
}

struct node* pop(struct node **qHead) {
	struct node *pt;
	if (*qHead == NULL)
		return NULL;
	pt = *qHead;
	*qHead = (*qHead)->next;
	return pt;
}

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

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

	while (qHead != NULL) {
		current = pop(&qHead);
		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;
	struct result *rt, *rtHead, *rtTemp;

	rtHead = malloc(sizeof(struct result));
	rt = rtHead;
	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]

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]

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.

thx in advance

[Jan]

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.

[sjn]

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!

hmmm, it's really helpful.
my problem is that i forgot to add 1 when i prune the part of recalculation.

[RC's]

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 ?

[renato_ferreira]

I try to use BFS, but I got WA. Can anyone help me?

Code: Select all

AC

Thank you.

[Jan]

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.

[renato_ferreira]

But I got WA, no TLE...

[Jan]

I just submitted your code and got TLE.

[renato_ferreira]

I changed my code, but got WA in 0.189.

Code: Select all

AC

Thank you.

[Jan]

Your current code fails for some cases. Check the I/O files.

Input
Output

Hope these help.

[renato_ferreira]

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.