题解 P2658 【汽车拉力比赛】
题解

从任意一个路标开始,做类dijkstra算法。

初始dis[]=0

dis[]记录到达该点的最小跨度,把加变成取max

每次确定路标dis的时候,ans=max(ans,dis[cur]),所有路标都访问到即得到ans

(其实会发现这就是prim)

下面是代码片段


struct iT
{
    int to, w;
    bool operator<(const iT &r) const {return w > r.w;}
}ss[M], *sp = ss;
int dis[N];
int iDijk(int ibeg)
{
    memset(dis, 0xFF, sizeof dis);
    int ret = 0, cur = 0;
    *sp++ = (iT){ibeg, 0};
    do
    {
        iT c = *ss;
        pop_heap(ss, sp--);
        if(dis[c.to] != -1)
            continue;
        dis[c.to] = c.w;
        if(bpt[c.to])
        {
            ret = max(ret, c.w);
            if(++cur == cpt)
                break;
        }
        for(iE *p = arrto[c.to]; p; p = p->next)
            if(dis[p->to] == -1)
            {
                *sp++ = (iT){p->to, max(c.w, p->w)};
                push_heap(ss, sp);
            }
    }
    while(ss != sp);
    return ret;
}
评论