POJ 2253 Frogger（最短路Floyd）题解

题意：想给你公青蛙位置，再给你母青蛙位置，然后给你剩余位置，问你怎么走，公青蛙全力跳的的最远距离最小。

思路：这里不是求最短路径，而是要你找一条路，青蛙走这条路时，对他跳远要求最低。这个思想还是挺好迁移的，原来我们用mp[i][j]表示i到j最短路径，那么我们现在用它表示i到j最大步伐，然后每次比较，只要最大步伐比他小，那么我们就走新的路。注意最后是mp[1][2]，一直mp[1][n]没改无限WA。

代码;

#include<cstdio> #include<set> #include<cmath> #include<stack> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int maxn = 200+5; const int INF = 0x3f3f3f3f; struct Node{double x,y; }node[maxn]; double mp[maxn][maxn]; //表示i->j的最大步伐 int Case = 1; void Floyd(int n){for(int k = 1;k <= n;k++){for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){if(mp[i][j] > max(mp[i][k],mp[k][j])){ //这样走最大步伐比较小mp[i][j] = mp[j][i]= max(mp[i][k],mp[k][j]);}}}}printf("Scenario #%d\nFrog Distance = %.3lf\n\n",Case++,mp[1][2]); } int main(){int n,m;while(~scanf("%d",&n) && n){for(int i = 1;i <= n;i++)scanf("%lf%lf",&node[i].x,&node[i].y);for(int i = 1;i <= n;i++){for(int j = i + 1;j <= n;j++){mp[i][j] = mp[j][i] = sqrt((node[i].x - node[j].x)*(node[i].x - node[j].x) +(node[i].y - node[j].y)*(node[i].y - node[j].y));}}Floyd(n);}return 0; }

 

转载于:https://www.cnblogs.com/KirinSB/p/9408735.html

总结

以上是生活随笔为你收集整理的POJ 2253 Frogger（最短路Floyd）题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。