记录编号	205704	评测结果	AAWAAATTTT
题目名称	不平凡的引线	最终得分	50
用户昵称	Collor	是否通过	未通过
代码语言	C++	运行时间	4.055 s
提交时间	2015-11-05 17:36:28	内存使用	3.56 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;
const int maxn=100100;
struct edge
{
	int y,v,next;
}e[maxn];
int linkk[maxn],q[maxn+maxn];
int vt[maxn],du[maxn];
bool vis[maxn],f[maxn];
int m,len=0;
long long ans=0;
inline int read()
{
	int x=0;char ch;
	ch=getchar();
	while (ch<'0'||ch>'9'){ch=getchar();}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x;
}
inline void insert(int xx,int yy,int vv)
{
	e[++len].next=linkk[xx]; linkk[xx]=len;
	e[len].y=yy; e[len].v=vv*10;
}
void init()
{
	memset(e,0,sizeof(e));
	memset(du,0,sizeof(du));
	memset(linkk,0,sizeof(linkk));
	cin>>m;
	int xx,yy,vv;
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&xx,&yy,&vv);
		insert(xx,yy,vv);
		insert(yy,xx,vv);
		du[xx]++;
		du[yy]++;
	}
}
void bfs()
{
	memset(q,0,sizeof(q));
	memset(f,true,sizeof(f));
	memset(vis,0,sizeof(vis));
	memset(vt,10,sizeof(vt));
	int head=0,tail=0;
	for (int i=1;i<=m+1;i++) {
		if (du[i]==1) {
			q[++tail]=i;
			vis[i]=1;
			vt[i]=0;
		}
	}
	int k=tail,tin=0;
	int minn=99999999;
	while (head<tail)
	{
		int tn=q[++head];
		for (int i=linkk[tn]; i ;i=e[i].next) {
			int tm=e[i].y;
			if (f[tm]){
				if (vt[tn]+e[i].v<vt[tm]) {
					vt[tm]=vt[tn]+e[tn].v;
					if (!vis[tm]){
						q[++tail]=tm;
						vis[tm]=1;
					}
					if ((vis[tn])&&(vt[tm]<minn))minn=vt[tm];
					//e[i].v--;
				//if (!e[i].v)
				}
			}
			else if (vt[tn]<vt[tm]+e[i].v && (e[i].v-vt[tn])/2>tin)
					tin=(e[i].v-vt[tn])/2;
		}
		f[tn]=0;
		if (head==k){
			k=tail;
			if (minn!=99999999){ 
				if (minn>tin)tin=0;
				ans=minn;
				minn=99999999;
			}
		}
	}
	double sum=(ans+tin)*1.0/10;
	printf("%.1f\n",sum);
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	init();
	bfs();
	return 0;
}