比赛 |
不平凡的世界 |
评测结果 |
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;
}