首页 > 代码库 > poj 2253 Frogger 解题报告
poj 2253 Frogger 解题报告
题目链接:http://poj.org/problem?id=2253
题目意思:找出从Freddy‘s stone 到 Fiona‘s stone 最短路中的最长路。 很拗口是吧,举个例子。对于 i 到 j 的一条路径,如果有一个点k, i 到 k 的距离 && k 到 j 的距离都小于 i 到 j 的距离,那么就用这两条中较大的一条来更新 i 到 j 的距离 。每两点之间都这样求出路径。最后输出 1 到 2 的距离(1:Freddy‘s stone 2:Fiona‘s stone )。
只能说,读题能力有待改进啊~~~一开始也读不懂题意 = =
还有就是 sqrt 的参数不能是整数啦= =,要是double 或 float。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 8 const int maxn = 200 + 10; 9 10 struct node11 {12 double x, y;13 }point[maxn];14 15 double dist[maxn][maxn];16 17 double distance(double x1, double x2, double y1, double y2)18 {19 double tx = x1 - x2;20 double ty = y1 - y2;21 return sqrt(tx*tx+ty*ty);22 }23 int main()24 {25 int n, l, f = 0, cas = 0;26 while (scanf("%d", &n) != EOF && n)27 {28 if (f)29 puts("");30 f = 1;31 for (l = 1; l <= n; l++)32 scanf("%lf%lf", &point[l].x, &point[l].y);33 for (int i = 1; i <= n; i++)34 {35 for (int j = i+1; j <= n; j++)36 dist[i][j] = dist[j][i] = distance(point[i].x, point[j].x, point[i].y, point[j].y);37 }38 // floyed39 for (int k = 1; k <= n; k++)40 {41 for (int i = 1; i <= n; i++)42 {43 for (int j = 1; j <= n; j++)44 {45 if (i != k && k != j && i != j && dist[i][j] > dist[i][k] && dist[i][j] > dist[j][k])46 {47 dist[i][j] = dist[j][i] = max(dist[i][k], dist[j][k]);48 }49 }50 }51 }52 printf("Scenario #%d\n", ++cas);53 printf("Frog Distance = %.3lf\n", dist[1][2]);54 }55 return 0;56 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。