记录编号	448707	评测结果	AAAAAAAAAA
题目名称	不平凡的引线	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2017-09-13 10:54:02	内存使用	5.28 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=100000+10;
struct Edge{
	int f,t,v,next;
}E[maxn*2];
int head[maxn];
int dis[maxn];
int in[maxn];
int vis[maxn];
queue<int>q;
int fa[maxn];
int edge=1;
inline void insert(int f,int t,int v){
	E[edge].t=t,E[edge].f=f,E[edge].v=v,E[edge].next=head[f],head[f]=edge++;
	E[edge].t=f,E[edge].f=t,E[edge].v=v,E[edge].next=head[t],head[t]=edge++;
}
inline int find(int x){
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}
int main(){
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	int m;
	scanf("%d",&m);
	int n;
	n=m+1;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		insert(x,y,z);
		in[x]++,in[y]++;
	}
	memset(dis,127/2,sizeof(dis));
	for(int i=1;i<=n;i++)
		if(in[i]==1){
			dis[i]=0;
			q.push(i);
			vis[i]=1;
		}
	double ans=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=E[i].next){
			int u=E[i].t;
			if(dis[u]>dis[x]+E[i].v){
				int fx=find(x);
				fa[u]=fx;
				dis[u]=dis[x]+E[i].v;
				if(!vis[u]){
					vis[u]=1;
					q.push(u);
				}
			}
		}
		vis[x]=0;
	}
	for(int i=1;i<=n;i++)
		find(i);
	for(int i=1;i<=m;i++){
		int x=i*2;
		int ff=fa[E[x].f],ft=fa[E[x].t];
		if(ff!=ft){
			int minn=min(dis[E[x].f],dis[E[x].t]);
			int maxx=max(dis[E[x].f],dis[E[x].t]);
			if(maxx-minn>=E[x].v)
				ans=max(ans,double(maxx));
			else ans=max(ans,double(maxx)+double(E[x].v-(maxx-minn))/2);
		}
	}
	printf("%.1lf\n",ans);
return 0;
}