比赛 不平凡的世界 评测结果 WWWTTTEEEE
题目名称 不平凡的引线 最终得分 0
用户昵称 Cydiater 运行时间 3.748 s
代码语言 C++ 内存使用 14.08 MiB
提交时间 2015-11-05 09:52:11
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <string>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
using namespace std;
int map[2000][2000],m,n,id[20000];
double ans=-1;
bool flag=0;
void init()
{
	cin>>m;
	memset(map,10,sizeof(map));
	memset(id,0,sizeof(id));
	for(int i=1;i<=m;i++)
	{
		int xx,yy,vv;
		cin>>xx>>yy>>vv;
		map[xx][yy]=vv;
		map[yy][xx]=vv;
		id[xx]++;	id[yy]++;
	}
	n=m+1;
	for(int i=1;i<=n;i++)
		map[i][i]=0;
}
void work()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(map[i][k]+map[k][j]<map[i][j])
					map[i][j]=map[i][k]+map[k][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(id[i]==1&&id[j]==1&&i!=j&&map[i][j]!=0)
			{
				flag=1;
				ans=max(ans,map[i][j]*1.0/2.0);
			}
	/*for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<map[i][j]<<' ';
		cout<<endl;
	}*/
	if(!flag)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i!=j)
				ans=max((double)(map[i][j]),ans);
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	init();
	work();
	cout<<ans<<endl;
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
	return 0;
}