CC On The Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 1684 Accepted Submission(s): 602
Problem Description
CC lives on the tree which has N nodes.On every leaf of the tree there is an apple(leaf means there is only one branch connect this node ) .Now CC wants to get two apple ,CC can choose any node to start and the speed of CC is one meter per second.
now she wants to know the shortest time to get two apples;
Input
Thers are many cases;
The first line of every case there is a number N(2<=N<=10000)
if n is 0 means the end of input.
Next there is n-1 lines,on the i+1 line there is three number ai,bi,ci
which means there is a branch connect node ai and node bi.
(1<=ai, bi<=N , 1<=ci<=2000)
ci means the len of the branch is ci meters ;
Output
print the mininum time to get only two apple;
Sample Input
7
1 2 1
2 3 2
3 4 1
4 5 1
3 6 3
6 7 4
0
Sample Output
Source
2011 Invitational Contest Host by BUPT
Recommend
chenyongfu | We have carefully selected several similar problems for you:
3849
3851
3854
3858
3857
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);
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
