首页 > 代码库 > poj 1553
poj 1553
题意:求1到2所有路径中最小蛙跳 蛙跳:在一条路径中所有蛙跳中的最大蛙跳
思路:dijska算法思想
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include<iostream> #include<cmath> using namespace std; struct Node { double x,y; }node[222]; double dist[222]; int s[222]; int n; int cas; double e(Node a,Node b) { return sqrt ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double max( double x, double y) { if (x>y) return x; return y; } void Dijsc() { int i,j,v; memset (s,0, sizeof (s)); for (i=1;i<=n;i++) dist[i]=e(node[1],node[i]); s[1]=1; for (i=1;i<=n;i++) { v=-1; double min=999999999; for (j=2;j<=n;j++) { if (dist[j]<min&&!s[j]) //每次选择最小蛙跳 向外扩展 所选择的这个蛙跳肯定是最小的 也就是最优的 v=j,min=dist[j]; } if (v==-1) break ;s[v]=1; for (j=2;j<=n;j++) //通过最小的蛙跳向外扩展 { if ((dist[j]>dist[v])&&(dist[j]>e(node[v],node[j]))) dist[j]=max(dist[v],e(node[v],node[j])); } } printf ( "Scenario #%d\n" ,cas); printf ( "Frog Distance = %.3f\n\n" ,dist[2]); } int main() { int i; cas=0; while ( scanf ( "%d" ,&n)!=EOF) { if (n==0) break ; cas++; for (i=1;i<=n;i++) scanf ( "%lf%lf" ,&node[i].x,&node[i].y); Dijsc(); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。