首页 > 代码库 > poj2253
poj2253
受此文启发,dijskstra的改动:http://blog.csdn.net/wangjian8006/article/details/7871812
#include<stdio.h> #include<string.h> #include<math.h> #define max(a,b) (a>b?a:b) double d[201]; typedef struct { int x,y; }n1; n1 point[201]; double distance(n1 a,n1 b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void dijskstra(int n) { double min; int vis[201],v,i; memset(vis,0,sizeof(vis)); for(i=2;i<=n;i++) d[i]=1e10; d[1]=0; d[1]=1; while(1) { min=1e10; for(i=1;i<=n;i++) { if(vis[i]==0&&min>d[i]) { v=i; min=d[i]; } } if(v==2) return; vis[v]=1; for(i=1;i<=n;i++) { if(vis[i]==0&&d[i]>max(d[v],distance(point[i],point[v]))) d[i]=max(d[v],distance(point[i],point[v])); } } } int main() { int n,i,exp; exp=0; while(scanf("%d",&n)&&n!=0) { exp++; for(i=1;i<=n;i++) scanf("%d%d",&point[i].x,&point[i].y); dijskstra(n); printf("Scenario #%d\n",exp); printf("Frog Distance = %.3lf\n\n",d[2]); } return 0; }
note:为了能用结构变量做形参,不能用c++里的结构体规则,至今不知为何……求高人指点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。