记录编号	205780	评测结果	AAAAAAAAAA
题目名称	不平凡的引线	最终得分	100
用户昵称	YXH_YXH	是否通过	通过
代码语言	C++	运行时间	0.490 s
提交时间	2015-11-05 18:49:46	内存使用	5.37 MiB

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
const int MAXN=100010,oo=2000000;
int N;//边数
struct edge{
	int y,v,next;
}e[MAXN*2];
int linkk[MAXN],len;//存图
int du[MAXN];//节点度
struct node{
	int x,v;
	friend bool operator < (node n1,node n2){return n1.v>n2.v;}
};
priority_queue <node> que;
long long dis[MAXN];
bool f[MAXN]={};//求最短路
int qq[MAXN*3]={};//队
double Max=-1.0*oo;
int x,y,v;//temp
inline void insert(int x,int y,int v){
	e[++len].next=linkk[x],linkk[x]=len;
	e[len].y=y,e[len].v=v;
}
void init(){
	cin>>N;
	for(int i=1; i<=N; i++){
		scanf("%d%d%d",&x,&y,&v);
		insert(x,y,v),insert(y,x,v);
		du[x]++,du[y]++;
	}
}
inline void Y_push(int x,int v){node temp;temp.x=x,temp.v=v;	que.push(temp);}
void dijkstra(){
	memset(dis,10,sizeof(dis));
	memset(f,0,sizeof(f));
	for(int i=1; i<=N+1; i++)//点
		if(du[i]==1){Y_push(i,0),dis[i]=0;}//进堆
	while(!que.empty())
	{
		int now=que.top().x,nex;	
		que.pop();
		if(f[now])continue;
		f[now]=1;
		for(int i=linkk[now]; i; i=e[i].next){
			nex=e[i].y;
			if(dis[now]+e[i].v<dis[nex]){
				dis[nex]=dis[now]+e[i].v;
				if(!f[nex])Y_push(nex,dis[nex]);
			}
		}
	}
	//for(int i=1; i<=N+1; i++)cout<<dis[i]<<endl;
}
void work(){
	memset(f,0,sizeof(f));
	int head=0,tail=0;
	for(int i=1; i<=N+1; i++)//点
		if(du[i]==1){qq[++tail]=1,f[1]=1;}//进队
	while(++head<=tail){
		int now=qq[head],nex;
		for(int i=linkk[now]; i; i=e[i].next){
			nex=e[i].y;
			if(!f[nex]){
				qq[++tail]=nex,f[nex]=1;
				int temp=abs(dis[now]-dis[nex]);//
				if(temp<e[i].v){
					double dist=(dis[now]+dis[nex]+e[i].v)*1.0/2;
					if(dist>Max)Max=dist;
				}
				temp=max(dis[now],dis[nex]);
				if(temp>Max)Max=1.0*temp;
			}
		}
	}
}
int main(){
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	
	init();
	dijkstra();
	work();
	printf("%.1lf\n",Max);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*

*/