记录编号	206118	评测结果	AAAAAAAAAA
题目名称	不平凡的引线	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	0.315 s
提交时间	2015-11-06 02:50:01	内存使用	4.75 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
	char c; int flag = 1;
    while((c = getchar()) < '0' || c > '9')
		if(c == '-') flag *= -1;
	x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
		x = (x<<3) + (x<<1) + (c-'0');
	x *= flag;
	return;
}
template<class Num>void write(Num x)
{
	if(!x) {putchar('0');return;}
    if(x < 0) putchar('-'), x = -x;
	static char s[20];int sl = 0;
	while(x) s[sl++] = x%10 + '0',x /= 10;
	while(sl) putchar(s[--sl]);
}

const int maxn = 200050, inf = 0x3f3f3f3f;

std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int> >, std::greater<std::pair<int,int> > > heap;

int N, M, F[maxn];
struct Edge
{
	int v, w, next;
	Edge(int v = 0,int w = 0,int next = 0): v(v), w(w), next(next){}
} edge[maxn];
int head[maxn], el;
int D[maxn];
bool flag[maxn], in[maxn];

void newedge(int u,int v,int w)
{
	edge[++el] = Edge(v, w, head[u]), head[u] =  el;
}
void init()
{
	int u, v, w;
	
	read(M), N = M + 1;
	
	for(int i = 1; i <= M; i++)
	{
		read(u), read(v), read(w);
		
		newedge(u, v, w);
		newedge(v, u, w);
		
		D[u]++, D[v]++;
	}
}
void solve()
{
	int ans = 0;
	
	for(int i = 1; i <= N; i++)
	{
		if(D[i] == 1)
			heap.push(std::make_pair(0, i));
		else
			F[i] = inf;
	}
	
	while(!heap.empty())
	{
		int t = heap.top().second;
		heap.pop();
		
		if(flag[t]) continue;
		
		flag[t] = true;
		
		for(int j = head[t]; j ; j = edge[j].next)
		{
			int v = edge[j].v, s = F[t] + edge[j].w;
			
			if(s < F[v]) heap.push(std::make_pair(F[v] = s, v));
		}
	}
	
	for(int i = 1; i <= N; i++)
	{
		for(int j = head[i]; j ; j = edge[j].next)
		{
			int v = edge[j].v;
			if(abs(F[i] - F[v]) == edge[j].w) continue;
			ans = std::max(ans, F[i] + F[v] + edge[j].w);	
		}
		ans = std::max(ans, F[i] << 1);
	}
	write(ans >> 1), putchar('.'), write((ans & 1) * 5);
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	
	init();
	
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}