OJ Board

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX_BUFF 1000
#define MAX 10000

struct Aresta {
	int o;
	int d;
	int t;
} a[MAX];

int pos[MAX];

int compare (struct Aresta *a, struct Aresta *b)
{
	if(a -> o == b -> o)
		return a -> d - b -> d;
	return a -> o - b -> o;
}

int Best (int x, int pai, int *best)
{
	int i;
	int num, max1 = 0, max2 = 0;
	for(i = pos[x]; ; i++) {
		if(a[i].o != x)
			break;
		if(a[i].d != pai) {
			/*printf("Best(%d, %d, %d)\n", a[i].d, x, *best);*/
			num = a[i].t + Best(a[i].d, x, best);
			/*printf("num = %d\n", num);*/
			if(num > max1) {
				max2 = max1;
				max1 = num;
			}
			else if(num > max2)
				max2 = num;
		}
	}
	/*printf("%d: %d %d\n", x, max1, max2);*/
	if(max1 + max2 > *best)
		*best = max1 + max2;
	return max1;
}

int main ()
{
	char c;
	char buff[MAX_BUFF];
	int count;
	int i;
	int best;
	int no1, no2, distancia;
	while(scanf("%c", &c) == 1) {
		if(c == '\n') {
			printf("0\n");
			scanf("%*c");
			continue;
		}
		ungetc(c, stdin);
		count = 0;
		while(fgets(buff, MAX, stdin) && buff[0] != '\n') {
			sscanf(buff, "%d %d %d", &no1, &no2, &distancia);
			a[count].o = a[count + 1].d = no1;
			a[count].d = a[count + 1].o = no2;
			a[count].t = a[count + 1].t = distancia;
			count += 2;
		}
		if(count > 0) {
			qsort(a, count, sizeof(struct Aresta), compare);
			for(i = 0; i < count; i++)
				if(i == 0 || a[i - 1].o != a[i].o)
					pos[a[i].o] = i;
				else
					pos[a[i].o] = pos[a[i - 1].o];
			best = 0;
			if(count == 2)
				best = 0;
			else
				Best(a[0].o, -1, &best);
			printf("%d\n", best);
		}
		else
			printf("0\n");
	}
	return 0;
}

Code: Select all

1 2 3
2 3 3
3 4 3

Code: Select all

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7




5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

Code: Select all

22
0
0
0
22

Code: Select all

22
0
0
22

Code: Select all

The problem statement is wrong.... This problem says "The area has up to 10,000 villages connected by road segments. The villages are numbered from 1. "-doesn't it mean that,nodes are numbered from 1 ?? That means the villages are numbered from 1,2,3,4,5,....,n.But I got WA thinking this.... the minimum & maximum node can be any number...but there difference will be always one... After coding in this way,I made this problem Accepted... :) 

Code: Select all

Remove After Accepted

Code: Select all

while(1) return Thanks.. 

Code: Select all

while(!EOF)

Code: Select all

while(!(-1))