比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的引线 最终得分 100
用户昵称 TARDIS 运行时间 0.246 s
代码语言 C++ 内存使用 4.13 MiB
提交时间 2017-09-05 20:52:01
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define XLM
using namespace std;
const int maxn=200010;

struct edge{
	int from,to,dist;
	//edge(int u,int v,int d):from(u),to(v),dist(d){}
};
vector <int> G[maxn];
vector <edge> E;

void add_edge(int from,int to,int dist){
	E.push_back((edge){from,to,dist});
	G[from].push_back(E.size()-1);
}

int n,m,k,in[maxn],dis[maxn];

void spfa(){
	queue <int> que;
	bool inque[maxn];
	memset(inque,0,sizeof(inque));
	memset(dis,127,sizeof(dis));
	for (int i=1;i<=n;i++){
		if (in[i]==1){
			dis[i]=0,que.push(i),inque[i]=1;
		}
	}
	while (!que.empty()){
		int u=que.front();que.pop(),inque[u]=0;
		for (int i=0;i<G[u].size();i++){
			edge &e=E[G[u][i]];
			if (dis[e.to]>dis[u]+e.dist){
				dis[e.to]=dis[u]+e.dist;
				if (!inque[e.to]) que.push(e.to),inque[e.to]=1;
			}
		}
	}
}


int main(){
#ifdef XLM
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
#endif
	scanf("%d",&m);n=m+1;
	for (int i=1;i<=m;i++){
		int from,to,dist;
		scanf("%d%d%d",&from,&to,&dist);
		add_edge(from,to,dist);
		add_edge(to,from,dist);
		in[from]++,in[to]++;
	}
	spfa();
	double ans=0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<G[i].size();j++){
			edge &e=E[G[i][j]];
			double x=(dis[i]+dis[e.to]+e.dist)/2.0;
			ans=max(ans,x);
		}
	}
	printf("%0.1f",ans);
	return 0;
}