题意：在一个三维的奶酪里面有n（n<=100）个洞，老鼠A想到达老鼠B的位置，在洞里面可以瞬间移动，在洞外面的移动速度为10秒一个单位，求最短时间
题解：如果两个洞相交，那么d[i][j]=0；如果不相交，那么d[i][j]=dist-(r[i]+r[j]),dist为这两个洞圆心之间的欧几里得距离
再用Dijkstra处理就可以了
#include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <algorithm> using namespace std; #define ll long long #define _cle(m, a) memset(m, a, sizeof(m)) #define repu(i, a, b) for(int i = a; i < b; i++) #define repd(i, a, b) for(int i = b; i >= a; i--) #define sfi(n) scanf("%d", &n) #define sfd(n) scanf("%lf", &n) #define pfi(n) printf("%d ", n) #define pfd(n) printf("%lf ", n) #define sfi2(n, m) scanf("%d%d", &n, &m) #define sfd2(n, m) scanf("%lf%lf", &n, &m) #define pfi2(n, m) printf("%d %d ", n, m) #define pfi3(a, b, c) printf("%d %d %d ", a, b, c) #define maxn 105 double dd[maxn][maxn]; struct Cir{ double x, y, z, r; }c[maxn]; double get_d(Cir c1, Cir c2) { return sqrt((c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y) + (c1.z - c2.z) * (c1.z - c2.z)); } const double inf = 1000000000000.0; struct Dijkstra { int n; //图,须手动传入！ double E[maxn][maxn], d[maxn]; int p[maxn]; //最短路径，父亲 void init(int n) { this->n = n; repu(i, 0, n) repu(j, 0, n) E[i][j] = dd[i][j]; } void solve(int s) { static bool vis[maxn]; memset(vis, 0, sizeof(vis)); memset(p, 255, sizeof(p)); repu(i, 0, n + 1) d[i] = inf; d[s] = 0.0; //repu(i, 0, n) pfd(d[i]); while(1) { int u = -1; for(int i = 0; i < n; i ++) { if(!vis[i] && (u == -1||d[i] < d[u])) { u = i; } } if(u == -1 || d[u] == inf) break; vis[u] = true; for(int v = 0; v < n; v ++) { if(d[u] + E[u][v] < d[v]) { d[v] = d[u] + E[u][v]; p[v] = u; } } } } } dij; int main() { int n; int kase = 0; while(~sfi(n) && n != -1) { kase++; repu(i, 1, n + 1) sfd2(c[i].x, c[i].y), sfd2(c[i].z, c[i].r); sfd2(c[0].x, c[0].y), sfd(c[0].z); sfd2(c[n + 1].x, c[n + 1].y), sfd(c[n + 1].z); c[0].r = c[n + 1].r = 0.0; repu(i, 0, n + 2) repu(j, 0, n + 2) { dd[i][j] = get_d(c[i], c[j]) - (c[i].r + c[j].r); if(dd[i][j] < 0.0) dd[i][j] = 0.0; //printf("%d %d %lf ", i, j, dd[i][j]); } dij.init(n + 2); dij.solve(0); //repu(i, 0, n + 2) pfd(dij.d[i]); printf("Cheese %d: Travel time = %d sec ", kase, (int)round(dij.d[n + 1] * 10.0)); } return 0; }