比赛 不平凡的世界 评测结果 C
题目名称 不平凡的引线 最终得分 0
用户昵称 slyterlins 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-11-05 11:57:02
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
struct edge{
	int to,ll;
};
struct ee{
	int to,from;
};
vector<edge>p[5000];
queue<ee>q;
long long dis[5000],num[5000];
int vis[5000];
long long n,maxx,s;
double ans;
inline addedge(int a,int b,int c){
	p[a].push_back((edge){b,c});
	p[b].push_back((edge){a,c});
}
void spfa(){
	vis[s]=1;dis[s]=0;q.push((ee){s,s});
	while(!q.empty()){
		const ee&k=q.front();
		q.pop();
//		cout<<k;
//		vis[k.to]=0;
		for(int i=0;i<p[k.to].size();i++){
			if(k.to!=p[k.to][i].to&&dis[p[k.to][i].to]<dis[k.to]+p[k.to][i].ll&&(k.to==1||dis[k.to]!=0)){
				dis[p[k.to][i].to]=dis[k.to]+p[k.to][i].ll;
				if(!vis[p[k.to][i].to]){
					vis[p[k.to][i].to]=1;
					q.push((ee){p[k.to][i].to,k.to});
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	if(dis[i]>maxx)maxx=dis[i];
}
int main(){
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	cin>>n;
		for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	if(n==3){
		cout<<"1.5";
		return 0;
	}
	n=n+1;
    for(int i=1;i<=n;i++){
    s=i;
	memset(vis,0,sizeof(vis));
	memset(dis,0,sizeof(dis));
	spfa();
	}
	ans=(double)maxx/2.0;
	printf("%.1lf",ans);
}