题目解析

问题理解

这是一个图论优化问题：在一个连通无向图中选择两个顶点建立传送门，使得从任意顶点出发，使用传送门后到达其他所有顶点的最短路径的最大值最小化。

关键观察

1. 问题本质：寻找最优传送门位置，使得图的直径（使用传送门后的最短路径直径）最小
2. 传送门效果：建立传送门(u,v)后，任意两点x,y之间的最短距离可能变为：
   • 原始距离 dis(x,y)
   • 通过传送门：dis(x,u) + dis(v,y) 或 dis(x,v) + dis(u,y)

算法框架

阶段一：预处理

首先计算图中所有顶点对之间的最短路径距离，使用经典的Floyd-Warshall算法，时间复杂度为O(n³)。

阶段二：候选生成与分组

生成所有可能的传送门候选对，并按它们在原始图中的距离进行分组。距离较远的顶点对作为传送门候选可能更有效，因为它们能显著缩短某些路径。

阶段三：最优答案搜索

采用从大到小的搜索策略：

• 从最大可能答案开始（图的原始直径）
• 逐步减小目标值，检查是否存在传送门设置能满足该约束
• 一旦找到满足条件的最小值，立即输出结果

核心检查机制

算法维护一个关键数据结构来高效验证可行性：

对于每个候选传送门(u,v)，检查是否满足：从任意顶点i出发，到其他所有顶点j的距离（使用传送门后）都不超过目标值D。

具体来说，对于每个起点i：

• 选择离i较近的传送门端点
• 计算通过该传送门能到达的最远距离
• 验证这个距离是否在允许范围内

算法优化点

1. 分组处理：按距离分组候选边，避免重复计算
2. 提前终止：一旦找到可行解立即返回
3. 增量更新：在检查过程中动态维护辅助信息
4. 剪枝策略：及时淘汰不满足条件的候选

复杂度分析

• 时间复杂度：O(n³) 对于n≤400完全可行
• 空间复杂度：O(n²) 存储距离矩阵和辅助数组

正确性保证

该算法能保证找到最优解，因为：

1. 枚举了所有可能的传送门位置
2. 系统性地验证了每个候选答案的可行性
3. 搜索顺序确保找到的是最小可行解

实际应用

这种"设施选址"类问题在现实中有很多应用：

• 网络服务器部署
• 交通枢纽规划
• 物流中心选址
• 通信网络优化

算法通过巧妙的预处理和系统性搜索，在合理时间内解决了这个NP难问题的特例。