uva 1001 say cheese dijstra

 题意：在一个奶酪中，有一些洞，一老鼠为了去追寻另外一只老鼠，决定从它所在位置走到另外一只老鼠的所在地，它每10s走1单位，在洞中可以瞬移，给定两只老鼠的坐标，以及洞的坐标和相应的半径。求最短路。

思路：起点和终点不走洞的话，当然直线距离最短，要考虑走洞的情况，每两个洞之间的最短距离最圆心距离减去两圆的半径，起点和终点视作半径为0的洞，给所有“洞”编号，距离用double保存中间结果，最后的答案4舍5入。

注意：两个洞间可能相交，会出现两点间的距离为负值，这时将它们的距离变为0即可

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#define Max(a,b) a>b?a:b
using namespace std;
const int maxn=110;
struct Node
{
	int x,y,z,r;
}node[maxn];
struct pt
{
	double d;
	int x;
	bool operator < (const pt &b)const
	{
		return d>b.d;
	}
};
int vis[maxn];
double d[maxn];
vector<int> g[maxn];
vector<double> w[maxn];
int n;
double dist(int i,int j)
{
	return sqrt((node[i].x-node[j].x)*(node[i].x-node[j].x)
	+(node[i].y-node[j].y)*(node[i].y-node[j].y)
	+(node[i].z-node[j].z)*(node[i].z-node[j].z))-node[i].r-node[j].r;
}
void dijstra(int s)
{
	priority_queue<pt,vector<pt> > q;
	for(int i=0;i<=n+1;i++)d[i]=1<<30;
	d[s]=0.0;
	q.push(pt{0.0,s});
	while(!q.empty())
	{
		pt a = q.top();q.pop();
		int x = a.x;
		
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<g[x].size();i++)
		{
			int v=g[x][i];
			if(d[v]>d[x]+w[x][i])
			{
				d[v]=d[x]+w[x][i];
				q.push({d[v]*1.0,v});
			}
		}
	}
}
int main()
{	
	int cas=0;
	while(scanf("%d",&n)&&n!=-1)
	{
		int x,y,z,r;
		memset(d,0,sizeof(d));
		memset(vis,0,sizeof(vis));
		for(int i=0;i<=n+1;i++)
		{
			g[i].clear();
			w[i].clear();
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&node[i].x,&node[i].y,&node[i].z,&node[i].r);
		}
		scanf("%d%d%d",&node[0].x,&node[0].y,&node[0].z);
		scanf("%d%d%d",&node[n+1].x,&node[n+1].y,&node[n+1].z);
		node[0].r=node[n+1].r=0;
		for(int i=0;i<=n;i++)
		for(int j=i+1;j<=n+1;j++)
		{
			double a = Max(0.0,dist(i,j));
			g[i].push_back(j);
			w[i].push_back(a);
			g[j].push_back(i);
			w[j].push_back(a);
		}
		dijstra(0);
		printf("Cheese %d: Travel time = %d sec\n",++cas,int(d[n+1]*10+0.5));//最终答案4舍5入 
	}
}