比赛 |
不平凡的世界 |
评测结果 |
WWWWWWWWWW |
题目名称 |
不平凡的引线 |
最终得分 |
0 |
用户昵称 |
Fmuckss |
运行时间 |
1.012 s |
代码语言 |
C++ |
内存使用 |
3.15 MiB |
提交时间 |
2015-11-05 11:37:16 |
显示代码纯文本
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>
#define maxn 100060
using namespace std;
bool vis1[maxn],vis2[maxn];
int m,n;
double ans,res;
queue<int> q,p;
struct node{
vector<int> ne;
vector<int> v;
int d,de;
bool le;
}ns[maxn];
void read(){
scanf("%d",&m);
n=m+1;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
ns[a].ne.push_back(b);
ns[a].v.push_back(c);
ns[b].ne.push_back(a);
ns[b].v.push_back(c);
ns[a].d++;if(ns[a].d==1){ns[a].le=true;}else ns[a].le=false;
ns[b].d++;if(ns[b].d==1){ns[b].le=true;}else ns[b].le=false;
}
}
void bfs1(){
while(!q.empty()){
int x=q.front();q.pop();
vis1[x]=true;
for(int i=0;i<ns[x].ne.size();i++){
int tmp=ns[x].ne[i];
if(ns[tmp].de>ns[x].de+ns[x].v[i]||!vis1[tmp]){
ns[tmp].de=ns[x].de+ns[x].v[i];
q.push(tmp);
}
}
}
}
void bfs2(){
p.push(1);
vis2[1]=true;
while(!p.empty()){
int x=p.front();p.pop();
for(int i=0;i<ns[x].ne.size();i++){
int tmp=ns[x].ne[i];
if(vis2[tmp])continue;
vis2[tmp]=true;
if(abs(ns[tmp].de-ns[x].de)!=ns[x].v[i]){
ans=((double)(ns[x].de+ns[tmp].de))/(double)2+((double)(ns[x].v[i]))/(double)2;
res=max(ans,res);
}
p.push(tmp);
}
}
}
void solve(){
for(int i=1;i<=n;i++){
if(ns[i].le){
q.push(i);
}
}
bfs1();
bfs2();
printf("%.1llf",res);
}
int main(){
freopen("firelead.in","r",stdin);
freopen("firelead.out","w",stdout);
read();
solve();
return 0;
}