题解 P2658 【汽车拉力比赛】

从任意一个路标开始，做类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; } ```