依旧板子题
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <queue> #include <cmath> using namespace std; const int maxn=100+10; double g[maxn][maxn]; const int inf=0x3f3f3f3f; struct node { double x,y,z; double r; }bb[maxn]; double getw(node a,node b) { double mm=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z); double nn=sqrt(mm)-a.r-b.r; if(nn<0) nn=0; return nn; } int n; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int Case=0; while(~scanf("%d",&n)) { if(n==-1) break; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&bb[i].x,&bb[i].y,&bb[i].z,&bb[i].r); } n=n+2; for(int i=n-1;i<=n;i++) { scanf("%lf%lf%lf",&bb[i].x,&bb[i].y,&bb[i].z); bb[i].r=0; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { g[i][j]=getw(bb[i],bb[j]); } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); printf("Cheese %d: Travel time = %.0f sec\n",++Case,floor(g[n-1][n]*10.0+0.5)); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8360627.html
