CF1016F Road Projects

Berland 王国有 $n$ 座城市，有些城市间由双向道路连接，每条边不会出现超过一次。且每一条边都有它自己的长度。城市从 $1$ 到 $n$ 编号。 城市 $u$ 与 $v$ 间的旅行时间为 从 $u$ 到 $v$ 的最短路径上的边的边权之和。 在 Berland 王国的两座最重要的城市是 $1$ 与 $n$ 。 Berland 王国交通运输部决定修建一条新道路，来分担最重要的城市间的交通压力。然而，很多人已习惯了他们间的现在的旅行时间，因此新建的道路不应造成较大的影响。 新的道路应该建在 $u$ 与 $v$ 间，其中 $u≠v$ 且当前 $u$ 与 $v$ 间不存在道路。 他们提出了 $m$ 种可能的工程。每项工程都含有新建道路的长度 $x$ 。 Polycarp 在 Berland 王国交通运输部担任首席分析师，处理这 $m $ 项工程是他的工作。对于第 $i$ 项工程，他被要求选择城市 $u$ 和 $v$ 去建造这条道路使得 最重要的城市间 的旅行时间尽可能长。 不幸的是，Polycarp 不是程序员，世界上没有分析师能够仅使用笔和纸来处理所有项目。 因此，他要求你帮助他对于每个项目计算最重要的城市之间的最大可能的旅行时间。注意，对于不同的项目， $u$ 和 $v$ 的选择可以不同。

无

无

The road network from the first example:  You can build the road with length $ 1 $ between cities $ 5 $ and $ 6 $ to get $ 83 $ as the travelling time between $ 1 $ and $ 7 $ ( $ 1 \rightarrow 2 \rightarrow 6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 7 $ $ = $ $ 18 + 4 + 1 + 12 + 24 + 24 = 83 $ ). Other possible pairs of cities will give answers less or equal to $ 83 $ .