1 条题解

  • 0
    @ 2025-9-10 0:12:00

    C++ :

    #define MAXN 1100UL
    
    #define D(x) ((double)(x))
    
    #include <cstdio>
    #include <queue>
    #include <cmath>
    
    using namespace std;
    
    queue<int> que;
    
    int x[MAXN],y[MAXN],r[MAXN],p,s,t,n,xt,yt;
    
    bool ex[MAXN];
    
    double dx[MAXN][2],eps=0.1;
    
    double ABS(double a){
    	return a>0?a:-a;
    }
    
    double Cal(int a,int b){
    	return sqrt(D(x[a]-x[b])*D(x[a]-x[b])+D(y[a]-y[b])*D(y[a]-y[b]));
    }
    
    int main(){
    	scanf("%d%d%d",&n,&xt,&yt);
    	for(int i=1;i<=n;i++){
    		scanf("%d%d%d",&x[i],&y[i],&r[i]);
    		if(x[i]==0&&y[i]==0){
    			s=i;
    		}
    		else if(x[i]==xt&&y[i]==yt){
    			t=i;
    		}
    	}
    	//bfs
    	dx[s][0]=dx[s][1]=10000.0;
    	que.push(s);ex[s]=1;
    	while(!que.empty()){
    		p=que.front();que.pop();
    		for(int i=1;i<=n;i++){
    			if(!ex[i]&&i!=p){
    				if(ABS(D(r[i]+r[p])-Cal(i,p))<=eps){
    					ex[i]=1;dx[i][0]=dx[p][0]*D(r[p])/D(r[i]);
    					dx[i][1]=dx[i][0]+dx[p][1];
    					if(i==t){
    						printf("%d",(int)dx[t][1]);
    						return 0;
    					}
    					que.push(i);
    				}
    			}
    		}
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    3241
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者