题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1245
思路:建图,0点为湖心,n+1点为湖外,然后bfs就可以了。。。具体见代码。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<cmath> 3 #include<queue> 4 #define p 1e-7 5 const int inf=1<<30; 6 const int MAXN=110; 7 using namespace std; 8 double dist[MAXN][MAXN]; 9 double cost[MAXN]; 10 int step[MAXN]; 11 int n,d; 12 struct Node{ 13 double x,y; 14 }node[MAXN]; 15 16 17 void bfs(int now){ 18 queue<int>Q; 19 cost[0]=0.0; 20 step[0]=0; 21 for(int i=1;i<=n+1;i++){ 22 cost[i]=inf*1.0; 23 step[i]=inf; 24 } 25 Q.push(now); 26 while(!Q.empty()){ 27 now=Q.front(); 28 Q.pop(); 29 for(int next=1;next<=n+1;next++){ 30 //如果满足条件或者能使步数减少 31 if(dist[now][next]<d+p 32 &&(dist[now][next]+cost[now]<cost[next] 33 ||(step[now]+1<step[next]))){ 34 Q.push(next); 35 step[next]=step[now]+1; 36 cost[next]=dist[now][next]+cost[now]; 37 } 38 } 39 } 40 } 41 42 43 44 45 int main(){ 46 while(~scanf("%d%d",&n,&d)){ 47 for(int i=1;i<=n;i++){ 48 scanf("%lf%lf",&node[i].x,&node[i].y); 49 } 50 if(d+p>42.5){ 51 printf("42.5 1\n"); 52 continue; 53 } 54 //建图1-n的点 55 for(int i=1;i<=n;i++){ 56 for(int j=1;j<=n;j++){ 57 if(i==j)dist[i][j]=0; 58 else dist[i][j]=sqrt(pow((node[i].x-node[j].x),2.0)+pow((node[i].y-node[j].y),2.0)); 59 } 60 } 61 //0点为湖心,n+1点为湖外 62 for(int i=1;i<=n;i++){ 63 dist[i][0]=dist[n+1][i]=inf; 64 dist[0][i]=fabs(sqrt(pow(node[i].x,2.0)+pow(node[i].y,2.0))-7.5); 65 dist[i][n+1]=min(fabs(fabs(node[i].x)-50.0),fabs(fabs(node[i].y)-50.0)); 66 } 67 dist[0][n+1]=inf*1.0; 68 bfs(0); 69 if(fabs(cost[n+1]-inf)<=p){ 70 printf("can't be saved\n"); 71 }else { 72 printf("%.2lf %d\n",cost[n+1],step[n+1]); 73 } 74 } 75 return 0; 76 } 77 78 79