zoj 1942 poj 2253 Frogger

本文主要是介绍zoj 1942 poj 2253 Frogger，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：在一个无向图中，求起点到终点的最短路径，而这条路径长度被定义为这条路径里最长的边。

思路：用floyd求出最短路径，只需修改一下递推方程， edge[i][j] = min(edge[i][j],max(edge[i][k],edge[k][j]))。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>using namespace std;const int inf = 10000000;
const int maxn = 205;struct point{double x,y;
};int n;
point a[maxn];
double edge[maxn][maxn];bool input(){cin>>n;if(n == 0) return false;for(int i = 0; i < n; i++){cin>>a[i].x>>a[i].y;}return true;
}
inline double dis(const point &a, const point &b){return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}void build(){for(int i = 0; i < n; i++){for(int j = i; j < n; j++){if(i == j) edge[i][j] = inf;else edge[i][j] = edge[j][i] = dis(a[i],a[j]);}}
}void floyd(){for(int k = 0; k < n; k++){for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){double w = max(edge[i][k],edge[k][j]);if(w < edge[i][j])edge[i][j] = w;}}}
}void solve(){static int cnt = 0;build();floyd();printf("Scenario #%d\n",++cnt);printf("Frog Distance = %.3lf\n",edge[0][1]);puts("");
}int main(){while(input()){solve();}return 0;
}

这篇关于zoj 1942 poj 2253 Frogger的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---