ACM-图论-最短路dijsktra poj2253

本文主要是介绍ACM-图论-最短路dijsktra poj2253，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题折磨了我一整天，一直撞南墙，疯狂改不同的小地方，再提交，最后，看别人的代码，发现是精度问题！！！！！double(%lf)计算—->float(%f)输出

题意：青蛙（单源点）分步跳跃到（终点）
每条路（源到终）定义权值为：各个路段中的最大值
求所有路中，权值最小的路，输出权值dis[n]
模板题，dijsktra;
希望好心的英语大佬可以给我说一下，题目中怎么表达是float输出而不是double

---

1.设置点

struct node{double x,y;//记录dis用 node(){}//等等要形成数组 
};
node no[205];

2.简化

double mul(node a,node b){//变成double double f=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);return sqrt(f);
}

3.main
模板：

多组输入{输入点初始化边edge(边权值）dij()输出dis[终点]
}

这题的套用

int z=1;//freopen("1.txt","r",stdin);while(scanf("%d",&n)!=EOF&&n){for(int i=1;i<=n;i++){scanf("%lf %lf",&no[i].x,&no[i].y);} init();dij();printf("Scenario #%d\nFrog Distance = %.3f\n\n",z++,dis[2]);////!!!!!精度问题，坑了我半天 }

4.很重要的初始化

void init(){for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(i==j)edge[i][j]=0;else edge[i][j]=edge[j][i]=mul(no[i],no[j]);//是无向图记得取反 //%d输出%lf会变成0 //min不可以直接对比double和int}}
}

5.我是重点dij
模板

{init(vis)init(dis)(源点到终点的距离）vis[源点]=1dis[源点]=0for(i:1-n){temp,curfor(1-n){找到从i出发的最小邻接点，temp,cur标记}vis[cur]=1for(1-n){更新各个点的dis}}
}

这题的套用

void dij(){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)dis[i]=edge[1][i];//全改成edgevis[1]=true;dis[1]=0;for(int i=1;i<n;i++){//<ndouble temp=inf;int cur=0;for(int j=1;j<=n;j++){if(!vis[j]&&temp>dis[j]){//>temp=dis[j];cur=j;}}vis[cur]=1;//printf("cur=%d  dis[cur]=%.3lf\n",cur,dis[cur]);//路中最大，找各路最小for(int j=1;j<=n;j++){if(!vis[j]&&dis[j]>max(dis[cur],edge[cur][j])){dis[j]=max(dis[cur],edge[cur][j]);}}}
}

6.数据范围

#define inf 0x3f3f3f3f
int s,n,m;
double dis[210],edge[210][210];
//点《=1000，边《=2000 
bool vis[210];

以上是我撞破头得来的dijsktra的经验之谈，欢迎大家参考！

这篇关于ACM-图论-最短路dijsktra poj2253的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---