CC On The Tree

7
1 2 1
2 3 2
3 4 1
4 5 1
3 6 3
6 7 4
0

5

ac代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<string>
#include<iostream>
#define INF 0xfffffff
#define min(a,b) (a>b?b:a)
using namespace std;
int n,ans;
struct node
{
	int u,v,w,next;
}edge[20200];
int head[10010],cnt,vis[10010],dig[10010];
void add(int u,int v,int w)
{
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
struct s
{
	int x,step;
	friend bool operator < (s a,s b)
	{
		return a.step>b.step;
	}
}a,temp;
int jud(struct s a)
{
	if(vis[a.x])
		return 0;
	if(a.step>ans)
		return 0;
	return 1;
}
int bfs(int x)
{
	a.x=x;
	a.step=0;
	priority_queue<struct s>q;
	q.push(a);
	memset(vis,0,sizeof(vis));
	vis[x]=1;
	while(!q.empty())
	{
		a=q.top();
		q.pop();
		int u=a.x;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].v;
			int w=edge[i].w;
			temp.x=v;
			temp.step=a.step+w;
			if(!jud(temp))
				continue;
			if(dig[v]==1)
				return temp.step;
			vis[v]=1;
			q.push(temp);
		}
	}
	return ans;
}
int main()
{
	while(scanf("%d",&n)!=EOF,n)
	{
		int i;
		cnt=0;
		memset(head,-1,sizeof(head));
		memset(dig,0,sizeof(dig));
		for(i=0;i<n-1;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
			dig[u]++;
			dig[v]++;
		}
		ans=INF;
		for(i=1;i<=n;i++)
		{
			if(dig[i]==1)
			{
				int tep=bfs(i);
				ans=min(ans,tep);
			}
		}
		printf("%d\n",ans);
	}
}

HDOJ 题目3848 CC On The Tree（BFS）

原文：http://blog.csdn.net/yu_ch_sh/article/details/45396141