比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的引线 最终得分 100
用户昵称 Arrow 运行时间 0.227 s
代码语言 C++ 内存使用 2.70 MiB
提交时间 2017-09-05 20:40:54
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define MAXM 100010
#define PB push_back
#define INF 0x7fffffff
struct Edge{ int u,v,len; };

	int m;
	vector <int> G[MAXM];
	vector <Edge> edges;
	queue <int> Q;
	int speed[MAXM]={0},cnt[MAXM]={0};
	int fire_t[MAXM]={0};
	bool vis[MAXM]={0};

void addedges(int x,int y,int w)
{
	edges.PB((Edge){x,y,w});
	edges.PB((Edge){y,x,w});
	int s=edges.size();
	G[x].PB(s-2);
	G[y].PB(s-1);
}

void prepare()
{
	for(int i=1;i<=m+1;i++)
	{
		fire_t[i]=INF;
		if(cnt[i]==1)
			speed[i]=1,Q.push(i),vis[i]=1,fire_t[i]=0;
	}
}

void work()
{
	while(!Q.empty())
	{
		int cur=Q.front();Q.pop();
		for(int i=0;i<(int)G[cur].size();i++)
		{
			Edge& e=edges[G[cur][i]];
			if(fire_t[e.v]>fire_t[cur]+e.len)
			{
				fire_t[e.v]=fire_t[cur]+e.len;
				speed[e.v]=1;
				if(!vis[e.v])
					Q.push(e.v);
			}
		}
	}
}

float getans()
{
	float ans=0.0;
	for(int i=1;i<=m+1;i++)
	{
		ans=max(ans,(float)fire_t[i]);
		for(int j=0;j<(int)G[i].size();j++)
		{
			Edge& e=edges[G[i][j]];
			if(fire_t[e.u]>fire_t[e.v]) continue;
			if(fire_t[e.v]!=fire_t[e.u]+e.len)
			{
				ans=max(ans,fire_t[e.v]+(float)(e.len-fire_t[e.v]+fire_t[e.u])/(float)2);
			}
		}
	}
	return ans;
}

int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,len;
		scanf("%d%d%d",&u,&v,&len);
		addedges(u,v,len);
		cnt[u]++,cnt[v]++;
	}
	prepare();
	work();
	printf("%.1f\n",getans());
return 0;
}