题意：
在一个三维的空间内求从起点到终点的最短时间花费。
其中n个洞，在洞内通过的时间花费是0，在洞外的时间花费是每单位10sec
思路：
水题
建立起点到每个洞的边，建立终点到每个洞的边，建立起点到终点的边 ，边权是到达所需的时间花费。求一次最短路即可。
code：
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<queue>using namespace std;const int maxn = 105;int n;struct ball{double x, y, z, r;ball(){}ball(double x_, double y_, double z_, double r_){x = x_;y = y_;z = z_;}}bb[maxn];double sx,sy,sz,ex,ey,ez;const int INF = 0x3f3f3f3f;const int MAXNODE = 110;struct Edge{int u, v;double dist;Edge() {}Edge(int u, int v, double dist) {this->u = u;this->v = v;this->dist = dist;}};struct HeapNode {int u;double d;HeapNode() {}HeapNode(double d, int u) {this->d = d;this->u = u;}bool operator < (const HeapNode& c) const {return d > c.d;}};struct Dijkstra {int n, m;vector<Edge> edges;vector<int> g[MAXNODE];bool done[MAXNODE];double d[MAXNODE];int p[MAXNODE];void init(int tot) {n = tot;for (int i = 0; i < n; i++)g[i].clear();edges.clear();}void add_Edge(int u, int v, double dist) {edges.push_back(Edge(u, v, dist));m = edges.size();g[u].push_back(m – 1);}void dijkstra(int s) {priority_queue<HeapNode> Q;for (int i = 0; i < n; i++) d[i] = (double)INF;d[s] = 0;memset(done, false, sizeof(done));Q.push(HeapNode(0, s));while (!Q.empty()) {HeapNode x = Q.top(); Q.pop();int u = x.u;if (done[u]) continue;done[u] = true;for (int i = 0; i < g[u].size(); i++) {Edge& e = edges[g[u][i]];if (d[e.v] > d[u] + e.dist) {d[e.v] = d[u] + e.dist;p[e.v] = g[u][i];Q.push(HeapNode(d[e.v], e.v));}}}}}gao;double dist(ball b1, ball b2){double tmp = (b1.x – b2.x)*(b1.x – b2.x) + (b1.y – b2.y) * (b1.y – b2.y) + (b1.z – b2.z) * (b1.z – b2.z);return sqrt(tmp);}void init(){double x,y,z,r;for(int i = 0; i < n; i++){scanf("%lf%lf%lf%lf",&x,&y,&z,&r);bb[i].x = x;bb[i].y = y;bb[i].z = z;bb[i].r = r;}scanf("%lf%lf%lf",&sx,&sy,&sz);scanf("%lf%lf%lf",&ex,&ey,&ez);gao.init(n+2);}void deal(){ball b1(sx,sy,sz,0);for(int i = 0; i < n; i++){double w = dist(b1, bb[i]);w = w – bb[i].r;if(w < 0) w = 0;gao.add_Edge(i, n, w*10);gao.add_Edge(n, i, w*10);}ball b2(ex,ey,ez,0);for(int i = 0; i < n; i++){double w = dist(b2, bb[i]);w = w – bb[i].r;if(w < 0) w = 0;gao.add_Edge(i, n+1, w*10);gao.add_Edge(n+1, i, w*10);}for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){double w = dist(bb[i], bb[j]);w = w – bb[i].r – bb[j].r;if(w < 0) w = 0;gao.add_Edge(i, j, w*10);gao.add_Edge(j, i, w*10);}}double w = dist(b1, b2);gao.add_Edge(n, n+1, w*10);gao.add_Edge(n+1, n, w*10);}void solve(){gao.dijkstra(n);printf("%d sec\n",(int)(gao.d[n+1]+0.5));}int main(){int cas = 0;while(scanf("%d",&n) != EOF){if(n == -1) break;init();deal();printf("Cheese %d: Travel time = ",++cas);solve();}return 0;}
注意最后的结果是四舍五入后的整形，这个地方wa了一发T_T
，使你疲倦的不是前面的高山，而是你鞋里的一粒沙子。
