比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
100 |
用户昵称 |
fyb |
运行时间 |
0.804 s |
代码语言 |
C++ |
内存使用 |
2.31 MiB |
提交时间 |
2015-11-05 09:33:20 |
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 100000
#define INF 1000000000
struct node{
int ind;
double t;
bool operator < (const node b)const{return t>b.t;}
};
struct edge{
int u,v,l;
};
double ans=0;
vector<edge> g[NMAX+1];
bool done[NMAX+1];
double ft[NMAX+1];
priority_queue<node> q;
double shao(double t1,double t2,int l){
if(t1+l<=t2)return t1+l;
else if(t1>=t2+l)return t2+l;
else return (t1+t2+l)/2.0;
}
int main(){
int m;
node tn;
int tu,tv,tl;
int i;
freopen("firelead.in","r",stdin);
freopen("firelead.out","w",stdout);
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d%d%d",&tu,&tv,&tl);
g[tu].push_back((edge){tu,tv,tl});
g[tv].push_back((edge){tv,tu,tl});
}
for(i=1;i<=m+1;i++)
if(g[i].size()==1){
q.push((node){i,0});
ft[i]=0;
}else ft[i]=INF;
while(!q.empty()){
tn=q.top();
q.pop();
if(done[tn.ind])continue;
done[tn.ind]=true;
for(i=0;i<g[tn.ind].size();i++){
edge& e=g[tn.ind][i];
if(ft[e.v]>ft[e.u]+e.l){
ft[e.v]=ft[e.u]+e.l;
if(!done[e.v])q.push((node){e.v,ft[e.v]});
}
if(done[e.v]&&shao(ft[e.u],ft[e.v],e.l)>ans)
ans=shao(ft[e.u],ft[e.v],e.l);
}
}
printf("%.1lf",ans);
return 0;
}