原题地址：点击打开链接
此题略坑。。。
#include<stdio.h> #include<string.h> #include<math.h> #define MAX 1<<31-1 struct Village { double x; double y; double r; }village[110]; int used[110],n; double dis[110],map[110][110],d; bool judge(int u,int v,double &l) { int i; Village v1=village[u]; Village v2=village[v]; l=sqrt((v1.x-v2.x)*(v1.x-v2.x)+(v1.y-v2.y)*(v1.y-v2.y)); if(l>(v1.r+v2.r) || l>d) //如果大于两圆的半径之和或者大于最长行走距离则排除 return false; return true; } double djks(int s) { memset(used,0,sizeof(used)); int i,j,u; double min; for(i=1;i<=n;i++) { dis[i]=map[s][i]; } dis[s]=0; used[s]=1; for(i=1;i<n;i++) { min=MAX; u=-1; //重点！！！！！！ for(j=1;j<=n;j++) { if(dis[j]<min && used[j]!=1) { min=dis[j]; u=j; } } if(u==-1) return min; used[u]=1; for(j=1;j<=n;j++) { if(used[j]!=1 &&dis[j]>dis[u]+map[u][j]) { dis[j]=dis[u]+map[u][j]; } } } return dis[n]; } int main() { int i,j; double l; while(scanf("%d",&n)!=EOF) { for(i=0;i<=n;i++) for(j=0;j<=n;j++) map[i][j]=MAX; for(i=1;i<=n;i++) { scanf("%lf%lf%lf",&village[i].x,&village[i].y,&village[i].r); } scanf("%lf%lf%lf",&village[0].x,&village[0].y,&village[0].r); d=village[0].r; for(i=1;i<n;i++) { for(j=i+1;j<=n;j++) { if(judge(i,j,l)) { map[i][j]=l; map[j][i]=l; } } } double res=djks(1); if(res!=MAX) printf("%.6lf\n",res); else printf("GAME OVER.\n"); } return 0; } /* 3 0 0 3 10 10 1 1 1 3 1 1 4 */