暑假集训(3)第四弹 -----Frogger(Poj2253)

时间:2023-03-09 04:12:22
暑假集训(3)第四弹 -----Frogger(Poj2253)

题意梗概:青蛙王子最近喜欢上了另一只经常坐在荷叶上的青蛙公主。不过这件事不小心走漏了风声,被某fff团团员知

道了,在青蛙王子准备倾述心意的那一天,fff团团员向湖泊中注入大量的充满诅咒力量的溶液。这种溶液最初练成需整

整十一年的时间,在每一个剁手节,都要向其中融入珍贵魔法材料“辛格多格的哀怨“。有“一碰到就会告白失败的”功用。

不过幸运的是,青蛙王子居然很快发现到i这一点,所以他准备通过某种神秘仪式,来驱散这个诅咒。但是这个仪式还需

要一个关键数来触发,那就是从青蛙王子所在荷叶跳到青蛙公主的,每一条路径中的最大跳跃步数的集合中的最小数。

有了它,”信仰之跃“仪式就可以开始发挥作用,破除”辛格多格的哀怨“的魔法力量。

为了保护真善美,为了爱与和平,你决定帮助青蛙王子得到那个最小数。

问题分析:我觉得这个星期做题都快做成懵逼了,好多种乱七八遭的算法,碰到题目都没怎么思考,就开始”套模板“,这

个题目,我套啊套,也没整出个名堂,最后还是百度了,用floyd算法或者prim什么的都行,然而我还是不会做,这真的很

难受。唉.....

 #include <cstdio>
#include <cmath>
int stone[][];
int x[],y[];
int n,cas=;
void mbegin()
{
int i;
for(i = ;i < n;i++)
scanf("%d%d",&x[i],&y[i]);
}
int max(int va,int vb)
{
return va > vb ? va : vb;
}
int square(int x1,int y1,int x2,int y2)
{
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
void init()
{
int i,j;
for(i = ;i < n;i++)
for(j = ;j < n;j++)
stone[i][j] =stone[j][i] = square(x[i],y[i],x[j],y[j]); }
double Floyd()
{
int i,j,k;
init();
for(k = ;k < n;k++)
for(i = ;i < n;i++)
for(j = ;j < n;j++)
{
if(stone[i][j] > stone[i][k] && stone[i][j] > stone[k][j])
stone[i][j] = max(stone[i][k],stone[k][j]);
stone[j][i] = stone[i][j];
}
return sqrt(double(stone[][]));
}
int main(void)
{
while(scanf("%d",&n) && n)
{
mbegin();
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++cas,Floyd());
}
return ; }