1001 - Say Cheese (Dijkstra算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了1001 - Say Cheese (Dijkstra算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2079字,纯文字阅读大概需要3分钟。
内容图文
![1001 - Say Cheese (Dijkstra算法)](/upload/InfoBanner/zyjiaocheng/1334/b432ac185dad400898197a6232829f40.jpg)
该题是求两点间的最短路问题,用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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。