首页 > 代码库 > POJ - 2253 Frogger（Floyd最短路+预处理）
POJ - 2253 Frogger（Floyd最短路+预处理）
题目链接：http://poj.org/problem?id=2253
题意：青蛙要从点1到点2，给出各点的坐标，如果点A到点B可以通过A->C，C->B，A到B的距离可以用A->C和C-B中较长的一边代替（如果A直接到B更短的话就不用了），求点1到点2的最短距离。
题解：本来想用dijkst，但是想想就200的数据量，直接Floyd岂不美滋滋。先预处理一下各点之间的距离。因为取两条边中较长的那条边，所以转移的话，那转移的两条边都要比原来的短才可以。
值得注意的是用C的格式输入的时候要用%lf，输出的时候用%f，这个是书上的一个小细节，忘了具体的原理了。（逃...
状态转移方程：dp[i][j]=max(dp[i][k],dp[k][j])
1 #include <cmath> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 int n,cas=1; 7 double dp[222][222]; 8 struct point{ 9 double x;10 double y;11 }P[222];12 13 double fun(point a,point b){14 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));15 }16 17 void Floyd(){18 for(int k=1;k<=n;k++)19 for(int i=1;i<=n;i++)20 for(int j=1;j<=n;j++)21 if(dp[i][j]>dp[i][k]&&dp[i][j]>dp[k][j])22 dp[i][j]=max(dp[i][k],dp[k][j]);23 }24 25 int main(){26 while(scanf("%d",&n)!=EOF&&n){27 for(int i=1;i<=n;i++) scanf("%lf %lf",&P[i].x,&P[i].y);28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=n;j++)30 dp[i][j]=fun(P[i],P[j]);31 Floyd();32 printf("Scenario #%d\nFrog Distance = %.3f\n\n",cas++,dp[1][2]);33 }34 return 0;35 }
POJ - 2253 Frogger（Floyd最短路+预处理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。