【AtCoder Regular Contest 064 E】Cosmic Rays | Mrsrz's blog

最短路。

题目大意：

给定平面上 $n$ 个圆形区域，要求从一个点走到另一个点，使得暴露在圆形区域外的路径尽可能少。求暴露在圆形区域外的路径的最小值。

题解：

把起点和终点看成半径为 $0$ 的圆形区域我们每次显然是从一个圆形区域，沿最短路走到另一个圆形区域。

两个圆形区域之间的最短路为其圆心距离减去两圆的半径。和 $0$ 取 $\max$。

跑 Dijkstra 即可。时间复杂度 $O(n^2)$。

注意这是一张完全图，所以用堆会更劣。

Code：

#include<cstdio>
#include<cmath>
const int N=1233;
int n,X[N],Y[N],R[N];
double dis[N];
bool vis[N];
inline double Dist(int x,int y){return sqrt(1.*x*x+1.*y*y);}
int main(){
    scanf("%d%d%d%d%d",X+1,Y+1,X+2,Y+2,&n),n+=2;
    for(int i=3;i<=n;++i)scanf("%d%d%d",X+i,Y+i,R+i);
    for(int i=2;i<=n;++i)dis[i]=1e18;
    for(int T=1;T<n;++T){
        int u=0;
        for(int i=1;i<=n;++i)
        if((!u||dis[i]<dis[u])&&!vis[i])u=i;
        vis[u]=1;
        for(int i=1;i<=n;++i)
        if(u!=i&&!vis[i]){
            double nd=Dist(X[u]-X[i],Y[u]-Y[i])-R[u]-R[i];
            if(nd<0)nd=0;
            if(dis[i]>dis[u]+nd)dis[i]=dis[u]+nd;
        }
    }
    printf("%.15f\n",dis[2]+1e-15);
    return 0;
}