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