用ans[i][j]表示从树i出发要到达树j，猴子每次能跳的最短距离的最大值。
然后以每个点为起点，做一个dijkstra，时间复杂度就是O(n*n*log(n))，
这样预处理之后，每次查询的复杂度就是O(1)的了。
每次做dijkstra的时候，初始化ans[i][j]=0(1<=j<=n),ans[i][i]=INF;
然后每次挑出一个最大的ans[i][j](1<=j<=n)，进行松弛操作。假设挑出的
当前最大的的序号为key，则
ans[i][j]=max(ans[i][j],min(ans[i][key],dis[key][j])) .

我当时的想法就是这样的，可是比赛的时候写砸了。
不知道算法是对是错，还请高手指点。

• DJ的时间复杂度会退化的吧，怎么都不可能小于|E|的吧 (351) acm06060 2007-10-30 18:42:28
  • 为什么回退化呢？感觉不会啊。 (0) Thank_you 2007-10-30 19:12:56
    • 你想总共e条边，dj不能不全部处理一遍吧，这样的话如果e=n2那么不就是n3了总共 (0) ACM06060 2007-10-30 19:16:53
      • 如果数据都是这样子，然后时间卡的很紧。那就只能摆明说是不让人过的，或者有更优秀的算法。 (0) Thank_you 2007-10-30 19:22:01