1001 - Say Cheese （Dijkstra算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了1001 - Say Cheese （Dijkstra算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2079字，纯文字阅读大概需要3分钟。
内容图文
该题是求两点间的最短路问题，用Dijkstra算法比较快 ，跑了0.003s 。
方法很简单，将圆看成结点，直接判断两个圆是否相交，如果相交距离为0，否则距离为圆心间距离减去两圆半径。 起点和终点也可以看成是一个半径为0的圆 。
这样就变成了两点间的最短路问题，适合用Dijkstra算法求解。 比较坑的是该题说了数据范围n最大100，但是我开了105竟然RE ，看成505就过了 。 所以在占用内存不多的情况下还是开大一点好 。
细节参见代码：
#include<bits/stdc++.h>
using namespace std;
const double INF = 1000000000;
const int maxn = 505;
int n,done[maxn],kase = 0;
double d[maxn];
double x,y,z,r;
struct node{
double x,y,z,r;
node(int x=0,int y=0,int z=0,int r=0) : x(x),y(y),z(z),r(r) {}
}a[maxn];
struct Node {
int from,to;
double d;
}e[maxn*maxn] ;
vector<int> g[maxn];
struct heapNode{
double d;
int u;
bool operator < (const heapNode& rhs) const {
return d > rhs.d;
}
};
double dijkstra(int s) {
priority_queue<heapNode> q;
for(int i=1;i<=n;i++) d[i] = INF , done[i] = 0;
d[s] = 0;
q.push((heapNode){0,s});
while(!q.empty()) {
heapNode x = q.top(); q.pop();
int u = x.u;
if(u == n) return d[u];
if(done[u]) continue;
done[u] = true;
for(int i=0;i<g[u].size();i++) {
Node& ed = e[g[u][i]];
if(d[ed.to] > d[u] + ed.d) {
d[ed.to] = d[u] + ed.d;
q.push((heapNode){d[ed.to],ed.to});
}
}
}
return -1;
}
int main() {
while(~scanf("%d",&n)&&n>=0) {
for(int i=1;i<=n;i++) {
scanf("%lf%lf%lf%lf",&x,&y,&z,&r);
a[i] = node(x,y,z,r);
}
scanf("%lf%lf%lf",&x,&y,&z); a[n+1] = node(x,y,z,0);
scanf("%lf%lf%lf",&x,&y,&z); a[n+2] = node(x,y,z,0);
n += 2;
int cnt = 0;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
Node ed,u;
double v = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z));
if(a[i].r+a[j].r >= v) ed.d = 0;
else ed.d = (v - a[i].r-a[j].r)*10;
ed.from = i; ed.to = j; u = ed; u.from = j; u.to = i;
e[cnt] = ed; g[i].push_back(cnt++);
e[cnt] = u; g[j].push_back(cnt++);
}
}
double ans = dijkstra(n-1);
printf("Cheese %d: Travel time = %.0f sec\n",++kase,ans);
for(int i=0;i<cnt;i++) g[i].clear();
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/weizhuwyzc000/article/details/47750353
内容总结
以上是互联网集市为您收集整理的1001 - Say Cheese （Dijkstra算法）全部内容，希望文章能够帮你解决1001 - Say Cheese （Dijkstra算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。