比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的引线 最终得分 100
用户昵称 fyb 运行时间 0.804 s
代码语言 C++ 内存使用 2.31 MiB
提交时间 2015-11-05 09:33:20
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 100000
#define INF 1000000000

struct node{
	int ind;
	double t;

	bool operator < (const node b)const{return t>b.t;}
};

struct edge{
	int u,v,l;
};

double ans=0;

vector<edge> g[NMAX+1];
bool done[NMAX+1];
double ft[NMAX+1];
priority_queue<node> q;

double shao(double t1,double t2,int l){
	if(t1+l<=t2)return t1+l;
	else if(t1>=t2+l)return t2+l;
	else return (t1+t2+l)/2.0;
}

int main(){
	int m;
	node tn;
	int tu,tv,tl;
	int i;

	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);

	scanf("%d",&m);
	for(i=0;i<m;i++){
		scanf("%d%d%d",&tu,&tv,&tl);
		g[tu].push_back((edge){tu,tv,tl});
		g[tv].push_back((edge){tv,tu,tl});
	}

	for(i=1;i<=m+1;i++)
		if(g[i].size()==1){
			q.push((node){i,0});
			ft[i]=0;
		}else ft[i]=INF;

	while(!q.empty()){
		tn=q.top();
		q.pop();

		if(done[tn.ind])continue;
		done[tn.ind]=true;
		for(i=0;i<g[tn.ind].size();i++){
			edge& e=g[tn.ind][i];
			if(ft[e.v]>ft[e.u]+e.l){
				ft[e.v]=ft[e.u]+e.l;
				if(!done[e.v])q.push((node){e.v,ft[e.v]});
			}
			if(done[e.v]&&shao(ft[e.u],ft[e.v],e.l)>ans)
				ans=shao(ft[e.u],ft[e.v],e.l);
		}
	}

	printf("%.1lf",ans);
	return 0;
}