题解 P2658 【汽车拉力比赛】
HOOCCOOH
2015-10-29 10:43:12
从任意一个路标开始,做类dijkstra算法。
初始dis[]=0
dis[]记录到达该点的最小跨度,把加变成取max
每次确定路标dis的时候,ans=max(ans,dis[cur]),所有路标都访问到即得到ans
(其实会发现这就是prim)
下面是代码片段
```cpp
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;
}
```