比赛 不平凡的世界 评测结果 AWWWWWWWWW
题目名称 不平凡的引线 最终得分 10
用户昵称 debug 运行时间 0.612 s
代码语言 C++ 内存使用 6.50 MiB
提交时间 2015-11-05 11:43:39
显示代码纯文本
#include<cstdio>
using namespace std;
int n;
int rudu[111111]={};
int weizhi[111111]={};
int weizhi2[111111]={};
int gen[111111]={};
int tou,wei;
int q[111111]={};
double t[111111]={};
bool vis[111111]={};
bool vis2[111111]={};
double v[222222]={};
int shuliang[111111]={};
struct ff
{
	int x,y;
	double v;
}f[111111]={};
int g[222222]={};
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	scanf("%d",&n);
	n++;
	for(int i=1;i<n;i++)
		scanf("%d%d%lf",&f[i].x,&f[i].y,&f[i].v),rudu[f[i].x]++,rudu[f[i].y]++;
	for(int i=1;i<=100000;i++)
		t[i]=1e+111;
	tou=0,wei=-1;
	for(int i=2;i<=100001;i++)
		weizhi[i]=weizhi2[i]=weizhi[i-1]+rudu[i-1];
	for(int i=1;i<n;i++)
		g[weizhi2[f[i].x]]=f[i].y,g[weizhi2[f[i].y]]=f[i].x,v[weizhi2[f[i].x]]=v[weizhi2[f[i].y]]=f[i].v,weizhi2[f[i].x]++,weizhi2[f[i].y]++;
	for(int i=1;i<=100000;i++)
		if(rudu[i]==1)
			q[++wei]=i,vis[i]=1,vis2[i]=1;
	for(int i=1;i<=100000;i++)
		shuliang[i]=rudu[i];
	//先确定根节点位置
	while(tou<=wei)
	{
		int te=q[tou];
		vis2[te]=1;
		for(int i=weizhi[te];i<weizhi[te+1];i++)
		{
			if(!vis2[g[i]])
				gen[te]=g[i],rudu[g[i]]--;
			if(rudu[g[i]]==1&&!vis[g[i]])
				q[++wei]=g[i],vis[g[i]]=1;
		}
		tou++;
	}//最后进队的自然是根节点
	tou=0,wei=-1;
	for(int i=1;i<=100000;i++)
		vis[i]=0;
	//开始点燃,计算每一个点到达最短时间
	for(int i=1;i<=100000;i++)
		rudu[i]=shuliang[i];
	for(int i=1;i<=n;i++)
		if(rudu[i]==1)
			t[i]=0,q[++wei]=i,vis[i]=1;
	while(tou<=wei)
	{
		int te=q[tou];
		for(int i=weizhi[te];i<weizhi[te+1];i++)
		{
			rudu[g[i]]--;
			if(t[g[i]]>t[te]+v[i])
				t[g[i]]=t[te]+v[i];
			if(rudu[g[i]]==1&&!vis[g[i]])
				q[++wei]=g[i],vis[g[i]]=1;
		}
		tou++;//bfs保证遍历顺序从叶子到跟
	}
	double ans=0;
	//下面枚举每一个点
	for(int i=1;i<=100000;i++)
	{
		double temp=t[i];
		for(int j=weizhi[i];j<weizhi[i+1];j++)
			if(gen[i]!=g[j])
			{
				if(temp<t[g[j]]+v[j])
					temp=(t[i]+t[g[j]]+v[j])/2;
			}
		if(ans<temp&&temp<1e+50)
			ans=temp;
	}
	printf("%.1lf\n",ans);
}