pku2631.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 75 行

#include <stdio.h>
#define SIZE 11000
typedef struct 
{
	int id;
	int dis;
	int next;
} Village;

Village v[33000];
int End = SIZE;
int visited[SIZE];
int distance[SIZE];
int maxdis, maxid;

void DFS(int id, int d)
{
	int pos = v[id].next;
	if (d > maxdis)
	{
		maxdis = d;
		maxid = id;
	}
	while (pos)
	{
		if (!visited[v[pos].id])
		{
			visited[v[pos].id] = 1;
			DFS(v[pos].id, d + v[pos].dis);
		}
		pos = v[pos].next;
	}
}


int main()
{
	int s, e, d, i, pos;
	i = 0;
	memset(v, 0, sizeof(v));
	while (scanf("%d %d %d", &s, &e, &d) != -1)
	{
		pos = s;
		while (v[pos].next) pos = v[pos].next;
		v[pos].next = End;
		v[End].id = e;
		v[End].dis = d;

		End++;
		
		pos = e;
		while (v[pos].next) pos = v[pos].next;
		v[pos].next = End;
		v[End].id = s;
		v[End].dis = d;

		End++;
	}
	maxdis = 0;
	maxid = 0;
	memset(distance, 0, sizeof(distance));
	memset(visited, 0, sizeof(visited));
	visited[1] = 1;
	DFS(1, 0);
	
	memset(distance, 0, sizeof(distance));
	memset(visited, 0, sizeof(visited));
	visited[maxid] = 1;
	DFS(maxid, 0);
	
	printf("%d\n", maxdis);
	return 0;
}