2406326_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INIT (Edge *)malloc(sizeof(Edge))
int n, m;
int visited[40001];

typedef struct node
{
	int adj;
	int w;
	struct node *next;
}Edge;

struct Node
{
	Edge *head;
}pot[40001];

struct NODE
{
	int v;
	int dis;
}queue[40001];
int f, r;
int no;
int d[40001];
int max = -1;

void bfs(int v)
{
	int mark;
	int dis;
	Edge *s;

	f = r = -1;
	queue[++f].v = v;
	queue[f].dis = 0;
	visited[v] = 1;
	no = 1;
	while(f!=r)
	{
		++r;
		mark = 1;
		s = pot[queue[r].v].head;
		dis = queue[r].dis;
		while(s->next)
		{
			if(!visited[s->next->adj])
			{
				mark = 0;
				visited[s->next->adj] = 1;
				queue[++f].v = s->next->adj;
				queue[f].dis = dis+s->next->w;
			}
			s = s->next;
		}
		if(mark&&dis>max)
			max = dis;
	}
}

int main()
{
	int i;
	Edge *s;
	int st, ed, w;
	char pos[2];

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
	{
		pot[i].head = INIT;
		pot[i].head->next = NULL;
	}
	memset(d,0,sizeof(d));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d%s",&st,&ed,&w,pos);
		st--,ed--;
		d[st]++,d[ed]++;
		s = INIT;
		s->adj = ed;s->w = w;
		s->next = pot[st].head->next;
		pot[st].head->next = s;
		s = INIT;
		s->adj = st;s->w = w;
		s->next = pot[ed].head->next;
		pot[ed].head->next = s;
	}
	for(i = 0; i < n; i++)
	{
		if(d[i]==1)
		{
			memset(visited,0,sizeof(visited));
			bfs(i);
		}
	}
	printf("%d\n",max);
	return 1;
}