比赛 不平凡的世界 评测结果 WWAWWWWWWW
题目名称 不平凡的引线 最终得分 10
用户昵称 WAHT 运行时间 0.581 s
代码语言 C++ 内存使用 10.90 MiB
提交时间 2015-11-05 10:50:16
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct que
{
	double value;
	int node;
	friend bool operator <(que a,que b)
	{	return a.value>b.value;	}
};
priority_queue<que> Q;
int read()
{
	int x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
const int oo=300000;
struct my
{
	int next,x,y,v;
}e[oo];
int linkk[oo],len,ru[oo];
void insert(int xx,int yy,int vv)
{
	e[++len].y=yy;
	e[len].x=xx;
	e[len].next=linkk[xx];
	linkk[xx]=len;
	e[len].v=vv;
	e[++len].y=xx;
	e[len].x=yy;
	e[len].next=linkk[yy];
	linkk[yy]=len;
	e[len].v=vv;
}
int q[oo],head,tail;
bool vis[oo];
double t[oo],ans;
int m;
void init()
{
	m=read();
	int a,b,v;
	for(int i=1;i<=m;i++)
	{a=read(),b=read(),v=read();ru[a]++,ru[b]++;	insert(a,b,v);}
	for(int i=1;i<=m+1;i++)
	if(ru[i]==1)
	{
		que a;
		a.value=e[linkk[i]].v;
		a.node=e[linkk[i]].y;
		Q.push(a);
		vis[i]=1;
	}
}
void bfs()
{
	while(!Q.empty())
	{
		
		int tn=Q.top().node;
		double v=Q.top().value;
		Q.pop();
		if(vis[tn]) continue;
		vis[tn]=1;
		t[tn]=v;
		ans=max(ans,v);
		for(int i=linkk[tn];i;i=e[i].next)
		{	
			int to=e[i].y;
			if(!vis[to])
			{	
				que a;
				a.value=v+e[i].v;
				a.node=to;
				Q.push(a);
			}
			else	if(vis[to])
			{
				ans=max(ans,v+(t[to]+e[i].v-v)/2);
			}
		
		}
	}
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	init();
	bfs();
	cout<<ans<<endl;
	return 0;
}