暑假集训(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 ; }