P2903 [USACO08MAR]麻烦的干草打包机The Loathesome Hay Baler
细节题。$O(n^{2})$的$bfs$可过。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cctype> 6 #include<cmath> 7 #define re register 8 using namespace std; 9 typedef double db; 10 void read(int &x){ 11 char c=getchar();x=0;int f=1; 12 while(!isdigit(c)) f&=(c!='-'),c=getchar(); 13 while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); 14 x=f?x:-x; 15 } 16 #define N 1052 17 const db eps=1e-8; 18 int sqr(int a){return a*a;} 19 struct node{int x,y,r;}a[N]; 20 int n,xt,yt,st,ed; 21 db d[N],v[N]; bool vis[N]; 22 db dist(node A,node B){return sqrt((db)(sqr(A.x-B.x)+sqr(A.y-B.y)));} 23 void dfs(int x){ 24 if(x==ed){ 25 cout<<(int)d[x]; 26 exit(0); 27 }//终点直接跳出 28 db tmp=v[x]*(db)a[x].r; 29 for(int i=1;i<=n;++i){ 30 if(i==x||vis[i]) continue; 31 if(fabs(dist(a[x],a[i])-(db)(a[x].r+a[i].r))<eps){//距离实时计算：两个齿轮相切 32 vis[i]=1; v[i]=tmp/(db)a[i].r; 33 d[i]=d[x]+v[i]; dfs(i); 34 } 35 } 36 } 37 int main(){ 38 read(n);read(xt);read(yt); 39 for(re int i=1;i<=n;++i){ 40 read(a[i].x);read(a[i].y);read(a[i].r); 41 if(a[i].x==xt&&a[i].y==yt) ed=i; 42 if(a[i].x==0&&a[i].y==0) st=i; 43 }v[st]=d[st]=10000;vis[st]=1;dfs(st); 44 }