比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
100 |
用户昵称 |
Arrow |
运行时间 |
0.227 s |
代码语言 |
C++ |
内存使用 |
2.70 MiB |
提交时间 |
2017-09-05 20:40:54 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define MAXM 100010
#define PB push_back
#define INF 0x7fffffff
struct Edge{ int u,v,len; };
int m;
vector <int> G[MAXM];
vector <Edge> edges;
queue <int> Q;
int speed[MAXM]={0},cnt[MAXM]={0};
int fire_t[MAXM]={0};
bool vis[MAXM]={0};
void addedges(int x,int y,int w)
{
edges.PB((Edge){x,y,w});
edges.PB((Edge){y,x,w});
int s=edges.size();
G[x].PB(s-2);
G[y].PB(s-1);
}
void prepare()
{
for(int i=1;i<=m+1;i++)
{
fire_t[i]=INF;
if(cnt[i]==1)
speed[i]=1,Q.push(i),vis[i]=1,fire_t[i]=0;
}
}
void work()
{
while(!Q.empty())
{
int cur=Q.front();Q.pop();
for(int i=0;i<(int)G[cur].size();i++)
{
Edge& e=edges[G[cur][i]];
if(fire_t[e.v]>fire_t[cur]+e.len)
{
fire_t[e.v]=fire_t[cur]+e.len;
speed[e.v]=1;
if(!vis[e.v])
Q.push(e.v);
}
}
}
}
float getans()
{
float ans=0.0;
for(int i=1;i<=m+1;i++)
{
ans=max(ans,(float)fire_t[i]);
for(int j=0;j<(int)G[i].size();j++)
{
Edge& e=edges[G[i][j]];
if(fire_t[e.u]>fire_t[e.v]) continue;
if(fire_t[e.v]!=fire_t[e.u]+e.len)
{
ans=max(ans,fire_t[e.v]+(float)(e.len-fire_t[e.v]+fire_t[e.u])/(float)2);
}
}
}
return ans;
}
int main()
{
freopen("firelead.in","r",stdin);
freopen("firelead.out","w",stdout);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int u,v,len;
scanf("%d%d%d",&u,&v,&len);
addedges(u,v,len);
cnt[u]++,cnt[v]++;
}
prepare();
work();
printf("%.1f\n",getans());
return 0;
}