这题就非常有意思了

首先，这是一道floyed妙用题

我们要对floyed进行简单的修改

先看下题意，要我们求青蛙距离

简单讲就是更小的跳跃距离，无视总路程

那么我们知道floyed是求最短路径的算法，并且是动态规划思想

那么我们只要将转移方程改改不就行了么

那么该怎么改哩

1.首先判断要改

floyed求最短路径是在找到更优路时更新

我们要改成：判断一条路是否可以分割成更短的两条路

如图：（比较粗糙不要介意233）

点A____________________点B
   \                  /
     \              /
       \          /
          点C   /
           
           

我们可以看出来AC或BC的长度是比AB短的

这就满足if条件

2.然后是处理

这就用AB，AC中更长的一个替换AB，即BC

为什么是更长的一个？

因为题目要求输出最大青蛙距离，就是最小值中的最大值

这样我们就有了核心代码：

for(res k=1;k<=m;++k)
    for(res i=1;i<=m;++i)
        for(res j=1;j<=m;++j)
            if(mmp[i][j]>mmp[i][k]&&mmp[i][j]>mmp[k][j]){
                mmp[i][j]=mmp[j][i]=max(mmp[i][k],mmp[k][j]);
            }

如果有不明白的，可以先模拟下

哪里讲的不好还请谅解，有问题可以私信我qwq