比赛 不平凡的世界 评测结果 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]);

}