1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6  7 typedef long long LL; 8 const int maxn = 100 + 5; 9 const int INF = 1e29;10 11 int n;12 int x[maxn], y[maxn], z[maxn], r[maxn], vis[maxn];13 double dist[maxn][maxn], d[maxn];14 15 struct HeapNode {16     double d;17     int u;18     bool operator < (const HeapNode& rhs) const {19         return d > rhs.d;20     }21 };22 23 LL dijkstra(int s) {24     memset(vis, 0, sizeof(vis));25     for (int i = 0; i <= n + 1; i++) d[i] = INF;26     priority_queue<HeapNode> q;27     d[0] = 0.0;28     q.push((HeapNode){0.0, 0});29     while (!q.empty()) {30         int u = q.top().u; q.pop();31         if (vis[u]) continue; vis[u] = 1;32         for (int i = 0; i <= n + 1; i++)33             if (d[i] > d[u] + dist[u][i]) {34                 d[i] = d[u] + dist[u][i];35                 q.push((HeapNode){d[i], i});36             }37     }38     return round(d[n + 1] * 10) + 0.5;39 }40 41 int main() {42     int kase = 0;43     while (scanf("%d", &n) == 1 && n != -1) {44         for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &y[i], &z[i], &r[i]);45         scanf("%d%d%d", &x[0], &y[0], &z[0]); r[0] = 0;46         scanf("%d%d%d", &x[n + 1], &y[n + 1], &z[n + 1]); r[n + 1] = 0;47         for (int i = 0; i <= n + 1; i++)48             for (int j = 0; j <= n + 1; j++) {49                 if (i == j) { dist[i][j] = 0.0; continue; }50                 dist[i][j] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2) + pow(z[i] - z[j], 2));51                 if (dist[i][j] <= r[i] + r[j]) dist[i][j] = 0.0;52                 else dist[i][j] = dist[i][j] - (r[i] + r[j]);53             }54         printf("Cheese %d: Travel time = %lld sec\n", ++kase, dijkstra(0));55     }56     return 0;57 }