1 solutions

  • 0
    @ 2025-11-5 17:29:32

    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

    Information

    ID
    18482
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By