比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
100 |
用户昵称 |
---- |
运行时间 |
0.532 s |
代码语言 |
C++ |
内存使用 |
11.21 MiB |
提交时间 |
2015-11-05 11:54:06 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool mint(T& a, T b) { return a > b ? a = b, true : false; }
template<class T> inline bool maxt(T& a, T b) { return a < b ? a = b, true : false; }
const int maxn = 233333;
struct ed
{
int v, w; ed * nx; ed() {}
ed(int _v, int _w, ed * _nx)
: v(_v), w(_w), nx(_nx) {}
} *G[maxn], mem[maxn << 1], *all = mem;
int n, que[maxn], dis[maxn], U[maxn], V[maxn], W[maxn];
bool inq[maxn];
int main()
{
freopen("firelead.in", "r", stdin);
#ifndef debug
freopen("firelead.out", "w", stdout);
#endif
scanf("%d", &n); ++n;
for (int i = 1; i < n; ++i)
{
int u, v, w; scanf("%d%d%d", &u, &v, &w);
w <<= 1;
G[u] = new(all++) ed(v, w, G[u]);
G[v] = new(all++) ed(u, w, G[v]);
U[i] = u; V[i] = v; W[i] = w;
}
memset(dis, 0x3f, sizeof(dis));
int qh(0), qt(0);
for (int i = 1; i <= n; ++i)
if (!G[i]->nx) inq[i] = true, dis[que[qt++] = i] = 0;
while (qh < qt)
{
int o = que[qh++]; inq[o] = false;
for (ed *p = G[o]; p; p = p->nx)
if (mint(dis[p->v], dis[o] + p->w) && !inq[p->v])
inq[que[qt++] = p->v] = true;
}
int ans = 0;
for (int i = 1; i <= n; ++i) maxt(ans, dis[i]);
for (int i = 1; i < n; ++i)
{
int u = U[i], v = V[i], w = W[i];
if (dis[u] > dis[v]) swap(u, v);
if (dis[v] - dis[u] < w) maxt(ans, dis[v] + (w - (dis[v] - dis[u])) / 2);
}
printf("%d.%c\n", ans >> 1, "05"[ans & 1]);
}