题意：一只母老鼠想要找到她的公老鼠玩具（cqww？），而玩具就丢在一个广阔的3维空间（其实可以想象成平面）上某个点，而母老鼠在另一个点，她可以直接走到达玩具的位置，但是耗时是所走过的欧几里得距离*10s。还有一种方法，就是靠钻洞，洞是球的，而在洞内怎么走都是不耗时间的。求母老鼠找到她的玩具所耗时？
思路：先要看清楚题意先！尽可能要找到洞，如果洞的半径越大，那么就可以越省时。如果老鼠和玩具都在同个洞上，那么不耗时即可找到。
其实就是求单源最短路，只是计算两点间的长度时要考虑到半径的。而且得注意两洞相连的情况，那么在两洞之间切换不需要时间。输出注意要用round(double)。
下面是dijkstra实现，比较快：
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=;
int x[N], y[N], z[N], r[N];
double dist[N][N];
double sdist[N];
int vis[N]; LL dijkstra(int n)
{
memset(vis,,sizeof(vis));
for(int i=; i<=n; i++) sdist[i]=1e29;
priority_queue<pdi,vector<pdi>,greater<pdi> > que;
que.push(make_pair(0.0, ));
sdist[]=0.0;
while(!que.empty())
{
int x=que.top().second;que.pop();
if(vis[x]) continue;
vis[x]=;
for(int i=; i<=n; i++)
{
if( sdist[i]>sdist[x]+dist[x][i] )
{
sdist[i]=sdist[x]+dist[x][i];
que.push(make_pair(sdist[i],i));
}
}
}
return round(sdist[n]*)+0.5;
} int main()
{
freopen("input.txt", "r", stdin);
int n;
int j=;
while(scanf("%d", &n), n>=)
{
memset(r,,sizeof(r));
for(int i=; i<=n; i++) scanf("%d %d %d %d",&x[i], &y[i], &z[i], &r[i]); scanf("%d %d %d",&x[],&y[],&z[]); //起点
scanf("%d %d %d",&x[n+],&y[n+],&z[n+]); //终点 //求两两之间的距离
for(int i=; i<=n+; i++)
{
for(int j=; j<=n+; j++)
{
dist[i][j]=0.0;
if(j!=i)
{
dist[i][j]=sqrt( pow(x[i]-x[j],)+pow(y[i]-y[j],)+pow(z[i]-z[j],) )-r[i]-r[j];
if(dist[i][j]<1e-) dist[i][j]=;
}
}
} printf("Cheese %d: Travel time = %lld sec\n", ++j, dijkstra(n+)); }
return ;
}
AC代码
下面是floyd实现，比较短：
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=;
int x[N], y[N], z[N], r[N];
double dist[N][N]; int main()
{
freopen("input.txt", "r", stdin);
int n;
int j=;
while(scanf("%d", &n), n>=)
{
memset(r,,sizeof(r));
for(int i=; i<=n; i++) scanf("%d %d %d %d",&x[i], &y[i], &z[i], &r[i]); scanf("%d %d %d",&x[],&y[],&z[]); //起点
scanf("%d %d %d",&x[n+],&y[n+],&z[n+]); //终点 //求两两之间的距离
for(int i=; i<=n+; i++)
{
for(int j=; j<=n+; j++)
{
dist[i][j]=0.0;
if(j!=i)
{
dist[i][j]=sqrt( pow(x[i]-x[j],)+pow(y[i]-y[j],)+pow(z[i]-z[j],) )-r[i]-r[j];
if(dist[i][j]<1e-) dist[i][j]=;
}
}
}
//floyd
for(int k=; k<=n+; k++)
for(int i=; i<=n+; i++)
for(int j=; j<=n+; j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
printf("Cheese %d: Travel time = %lld sec\n", ++j, (LL)(round(dist[][n+]*)+0.5) ); }
return ;
}
AC代码