1 solutions
-
0
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