记录编号	283714	评测结果	AAAAAAAAAA
题目名称	不平凡的引线	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.370 s
提交时间	2016-07-15 11:10:23	内存使用	4.60 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 100005;
int n,m;
int dis[maxn];//每个节点到叶节点的最近距离
struct edge{
	int from,w,to,next;
}lst[maxn*2];
int first[maxn],degree[maxn];
int len=1;
void insert(int v1,int v2,int d){
	lst[len].from = v1;
	lst[len].to = v2;
	lst[len].w = d;
	lst[len].next = first[v1];
	first[v1]=len++;
}
bool visited[maxn];
int T;
void bfs(int s){
	++T;
	queue<int> q;
	q.push(s);
	dis[s]=0;
	visited[s]=T;
	while(!q.empty()){
		int j = q.front();
		q.pop();
		for(int pt = first[j];pt;pt = lst[pt].next){
			if(visited[lst[pt].to]!=T){
				visited[lst[pt].to] = T;
				if(dis[lst[pt].to]>dis[j]+lst[pt].w){
					dis[lst[pt].to]=dis[j]+lst[pt].w;
					q.push(lst[pt].to);
				}
			}
		}
	}
}
int main(){
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	scanf("%d",&m);
	memset(dis,127,sizeof(dis));
	n = m+1;
	int a,b,c;
	for(int i = 1;i<=m;++i){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c);
		insert(b,a,c);
		degree[a]++;
		degree[b]++;
	}
	for(int i = 1;i<=n;++i){
		if(degree[i]==1){
			bfs(i);
		}
	}
	int latest = dis[1];
	for(int i = 1;i<=n;++i){
		if(dis[i]>latest)latest = dis[i];
	}
	double ans = latest/1.0;
	for(int i = 1;i<len;i+=2){
		a = dis[lst[i].from];b=dis[lst[i].to];c=lst[i].w;
		if((a+c==b)||(b+c==a))continue;
		else{
			double now = 0;
			if(a>b){
				c-=(a-b);
				now=a;
			}
			else if(a<b){
				c-=(b-a);
				now=b;
			}else{
				now=a;
			}
			now+=c/2.0;
			if(now>ans)ans=now;
		}
		
	}
	printf("%.1lf\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}