比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
100 |
用户昵称 |
TARDIS |
运行时间 |
0.246 s |
代码语言 |
C++ |
内存使用 |
4.13 MiB |
提交时间 |
2017-09-05 20:52:01 |
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define XLM
using namespace std;
const int maxn=200010;
struct edge{
int from,to,dist;
//edge(int u,int v,int d):from(u),to(v),dist(d){}
};
vector <int> G[maxn];
vector <edge> E;
void add_edge(int from,int to,int dist){
E.push_back((edge){from,to,dist});
G[from].push_back(E.size()-1);
}
int n,m,k,in[maxn],dis[maxn];
void spfa(){
queue <int> que;
bool inque[maxn];
memset(inque,0,sizeof(inque));
memset(dis,127,sizeof(dis));
for (int i=1;i<=n;i++){
if (in[i]==1){
dis[i]=0,que.push(i),inque[i]=1;
}
}
while (!que.empty()){
int u=que.front();que.pop(),inque[u]=0;
for (int i=0;i<G[u].size();i++){
edge &e=E[G[u][i]];
if (dis[e.to]>dis[u]+e.dist){
dis[e.to]=dis[u]+e.dist;
if (!inque[e.to]) que.push(e.to),inque[e.to]=1;
}
}
}
}
int main(){
#ifdef XLM
freopen("firelead.in","r",stdin);
freopen("firelead.out","w",stdout);
#endif
scanf("%d",&m);n=m+1;
for (int i=1;i<=m;i++){
int from,to,dist;
scanf("%d%d%d",&from,&to,&dist);
add_edge(from,to,dist);
add_edge(to,from,dist);
in[from]++,in[to]++;
}
spfa();
double ans=0;
for (int i=1;i<=n;i++){
for (int j=0;j<G[i].size();j++){
edge &e=E[G[i][j]];
double x=(dis[i]+dis[e.to]+e.dist)/2.0;
ans=max(ans,x);
}
}
printf("%0.1f",ans);
return 0;
}