1001

题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=3442&mosmsg=Submission+received+with+ID+26564769

小老鼠可以直接看成直径为 (0) 的洞，也可以特别判断

如果两个洞相交，则两洞之间花费为 (0), 否则花费为 ((d(i,j)-r[i]-r[j])*10)

最短路即可

特别注意：四舍五入至整数时使用 (.0f) 或 ((int)(ans+0.5))，否则若直接转换是直接舍掉小数位

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double, int> pdi;

const int maxn = 1010;
const double INF = 1000000007;

int n;
int s, t;
double x[maxn], y[maxn], z[maxn], r[maxn];

int h[maxn], cnt = 0;
struct E{
	int to;
	double cost;
	int next;
}e[maxn * maxn * 10];
void add(int u, int v, double w){
	e[++cnt].to = v;
	e[cnt].cost = w;
	e[cnt].next = h[u];
	h[u] = cnt;
}

double sqr(double x){
	return x * x;
}

double dis(int i, int j){
	return sqrt(sqr(1.0 * (x[i] - x[j])) + sqr(1.0 * (y[i] - y[j])) + sqr(1.0 * (z[i] - z[j])));
}

void make_edge(){
	for(int i = 1 ; i <= n ; ++i){
		for(int j = i + 1 ; j <= n ; ++j){
			double di = dis(i, j);
			if(di - r[i] - r[j] < 0){ // 相交 
				add(i, j, 0);
				add(j, i, 0); 
			} else{
				double w = (di - r[i] - r[j]) * 10;
				add(i, j, w);
				add(j, i, w);
			}
		}
	}
}

double d[maxn];
void dij(){
	priority_queue<pdi, vector<pdi>, greater<pdi> > q;
	for(int i = 1 ; i <= n + 2 ; ++i) d[i] = INF;

	d[s] = 0;
	q.push(pdi(d[s], s));
	
	while(!q.empty()){
		pdi p = q.top(); q.pop();
		int u = p.second;
		
		if(d[u] - p.first < 0) continue; 
		
		for(int i = h[u] ; i != -1 ; i = e[i].next){
			int v = e[i].to;
//			printf("%d %d %lf
", u, v, e[i].cost);
			if(d[v] - (d[u] + e[i].cost) > 0){
				d[v] = d[u] + e[i].cost;
				q.push(pdi(d[v], v));
			}
		}
	}
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	int kase = 0;
	while(scanf("%d", &n) && n != -1){
		memset(h, -1, sizeof(h)); cnt = 0;
		
		for(int i = 1 ; i <= n ; ++i){
			scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
		}
		scanf("%lf%lf%lf", &x[n + 1], &y[n + 1], &z[n + 1]);
		scanf("%lf%lf%lf", &x[n + 2], &y[n + 2], &z[n + 2]);
		r[n + 1] = 0, r[n + 2] = 0;
		
		s = n + 1, t = n + 2;
		n += 2;
		
		make_edge();
		
		dij();
		
		printf("Cheese %d: Travel time = %d sec
", ++kase, (int)(d[t] + 0.5));
	}
	return 0;
}