> 用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])) .
> 
> 我当时的想法就是这样的，可是比赛的时候写砸了。
> 不知道算法是对是错，还请高手指点。

• 为什么回退化呢？感觉不会啊。 (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