记录编号	205692	评测结果	AAWAAAWAWA
题目名称	不平凡的引线	最终得分	70
用户昵称	Fmuckss	是否通过	未通过
代码语言	C++	运行时间	1.057 s
提交时间	2015-11-05 17:30:35	内存使用	3.15 MiB

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>
#define maxn 100060
#define inf 1e+9 
using namespace std;
bool vis1[maxn],vis2[maxn];
int m,n;
double ans,res;
queue<int> q,p;
struct node{
	vector<int> ne;
	vector<int> v;
	int d,de;
	bool le;
	node(){de=inf;}
}ns[maxn];
void read(){
	scanf("%d",&m);
	n=m+1;
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		ns[a].ne.push_back(b);
		ns[a].v.push_back(c);
		ns[b].ne.push_back(a);
		ns[b].v.push_back(c);
		ns[a].d++;if(ns[a].d==1){ns[a].le=true;}else ns[a].le=false;
		ns[b].d++;if(ns[b].d==1){ns[b].le=true;}else ns[b].le=false;
	}
}
void bfs1(){
	while(!q.empty()){
		int x=q.front();q.pop();
		vis1[x]=true;
		for(int i=0;i<ns[x].ne.size();i++){
			int tmp=ns[x].ne[i];	
			if(ns[tmp].de>ns[x].de+ns[x].v[i]||!vis1[tmp]){
				ns[tmp].de=ns[x].de+ns[x].v[i];
				q.push(tmp);
			}
		}
	}
}
void bfs2(){
	p.push(1);
	vis2[1]=true;
	while(!p.empty()){
		int x=p.front();p.pop();
		for(int i=0;i<ns[x].ne.size();i++){
			int tmp=ns[x].ne[i];
			if(vis2[tmp])continue;
			vis2[tmp]=true;
			double tmp2=fabs(ns[tmp].de-ns[x].de);
			ans=(double)min(ns[x].de,ns[tmp].de)+
				(double)(max((double)0,(double)ns[x].v[i]-tmp2))/(double)2+
				min(tmp2,(double)ns[x].v[i]);
			res=max(res,ans);
			p.push(tmp);
		}
	}
} 
void solve(){
	for(int i=1;i<=n;i++){
		if(ns[i].le){
			ns[i].de=0;
			q.push(i);
		}
	}
	bfs1();
	bfs2();
	printf("%.1lf",res);
}
int main(){
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	read();
	solve();
	return 0;
}