比赛 |
不平凡的世界 |
评测结果 |
AWWWWWWWWW |
题目名称 |
不平凡的引线 |
最终得分 |
10 |
用户昵称 |
debug |
运行时间 |
0.612 s |
代码语言 |
C++ |
内存使用 |
6.50 MiB |
提交时间 |
2015-11-05 11:43:39 |
显示代码纯文本
#include<cstdio>
using namespace std;
int n;
int rudu[111111]={};
int weizhi[111111]={};
int weizhi2[111111]={};
int gen[111111]={};
int tou,wei;
int q[111111]={};
double t[111111]={};
bool vis[111111]={};
bool vis2[111111]={};
double v[222222]={};
int shuliang[111111]={};
struct ff
{
int x,y;
double v;
}f[111111]={};
int g[222222]={};
int main()
{
freopen("firelead.in","r",stdin);
freopen("firelead.out","w",stdout);
scanf("%d",&n);
n++;
for(int i=1;i<n;i++)
scanf("%d%d%lf",&f[i].x,&f[i].y,&f[i].v),rudu[f[i].x]++,rudu[f[i].y]++;
for(int i=1;i<=100000;i++)
t[i]=1e+111;
tou=0,wei=-1;
for(int i=2;i<=100001;i++)
weizhi[i]=weizhi2[i]=weizhi[i-1]+rudu[i-1];
for(int i=1;i<n;i++)
g[weizhi2[f[i].x]]=f[i].y,g[weizhi2[f[i].y]]=f[i].x,v[weizhi2[f[i].x]]=v[weizhi2[f[i].y]]=f[i].v,weizhi2[f[i].x]++,weizhi2[f[i].y]++;
for(int i=1;i<=100000;i++)
if(rudu[i]==1)
q[++wei]=i,vis[i]=1,vis2[i]=1;
for(int i=1;i<=100000;i++)
shuliang[i]=rudu[i];
//先确定根节点位置
while(tou<=wei)
{
int te=q[tou];
vis2[te]=1;
for(int i=weizhi[te];i<weizhi[te+1];i++)
{
if(!vis2[g[i]])
gen[te]=g[i],rudu[g[i]]--;
if(rudu[g[i]]==1&&!vis[g[i]])
q[++wei]=g[i],vis[g[i]]=1;
}
tou++;
}//最后进队的自然是根节点
tou=0,wei=-1;
for(int i=1;i<=100000;i++)
vis[i]=0;
//开始点燃,计算每一个点到达最短时间
for(int i=1;i<=100000;i++)
rudu[i]=shuliang[i];
for(int i=1;i<=n;i++)
if(rudu[i]==1)
t[i]=0,q[++wei]=i,vis[i]=1;
while(tou<=wei)
{
int te=q[tou];
for(int i=weizhi[te];i<weizhi[te+1];i++)
{
rudu[g[i]]--;
if(t[g[i]]>t[te]+v[i])
t[g[i]]=t[te]+v[i];
if(rudu[g[i]]==1&&!vis[g[i]])
q[++wei]=g[i],vis[g[i]]=1;
}
tou++;//bfs保证遍历顺序从叶子到跟
}
double ans=0;
//下面枚举每一个点
for(int i=1;i<=100000;i++)
{
double temp=t[i];
for(int j=weizhi[i];j<weizhi[i+1];j++)
if(gen[i]!=g[j])
{
if(temp<t[g[j]]+v[j])
temp=(t[i]+t[g[j]]+v[j])/2;
}
if(ans<temp&&temp<1e+50)
ans=temp;
}
printf("%.1lf\n",ans);
}