题目分析

本题要求在无向图中，找到Elaxia（路径为 $x_1 \to y_1$）和w**（路径为 $x_2 \to y_2$）的最短路径中，最长的公共路径长度。核心在于筛选出同时属于两条最短路径的边，再从中找到最长的连续路径。

算法标签

图论、

Dijkstra算法、

拓扑排序、

动态规划（DP）、

最短路径

算法思路

1. 计算关键最短距离

首先，使用Dijkstra算法计算4个最短距离数组：

• $dx1[u]$：从 $x_1$ 到 $u$ 的最短距离
• $dy1[u]$：从 $y_1$ 到 $u$ 的最短距离（用于判断边是否在 $x_1 \to y_1$ 的最短路径上）
• $dx2[u]$：从 $x_2$ 到 $u$ 的最短距离
• $dy2[u]$：从 $y_2$ 到 $u$ 的最短距离（用于判断边是否在 $x_2 \to y_2$ 的最短路径上）

2. 筛选公共有效边

一条边 $(u, v, w)$ 能成为两条最短路径的公共边，需满足以下条件之一（因为路径方向可能相反）：

• 对于 $x_1 \to y_1$ 的最短路径：$dx1[u] + w + dy1[v] = dx1[y_1]$（或 $dx1[v] + w + dy1[u] = dx1[y_1]$）
• 对于 $x_2 \to y_2$ 的最短路径：$dx2[u] + w + dy2[v] = dx2[y_2]$（或 $dx2[v] + w + dy2[u] = dx2[y_2]$）

满足上述条件的边构成一个有向无环图（DAG），因为最短路径中不存在环（否则可通过移除环缩短路径）。

3. 求DAG中的最长路径

在筛选出的DAG上，通过拓扑排序结合动态规划求最长路径：

• 拓扑排序：处理DAG的依赖关系，确保按顺序计算每个节点的最长路径
• 动态规划：$dp[u]$ 表示到达节点 $u$ 的最长公共路径长度，对于边 $(u \to v, w)$，有 $dp[v] = \max(dp[v], dp[u] + w)$

由于公共路径可能有两种方向（顺向和反向），需对两种方向的DAG分别计算最长路径，最终取最大值。

复杂度分析

• Dijkstra算法：对4个起点各执行一次，每次时间复杂度为 $O(m \log n)$（使用优先队列），总复杂度 $O(4m \log n)$
• 筛选有效边：遍历所有 $m$ 条边，复杂度 $O(m)$
• 拓扑排序与DP：处理DAG的边，复杂度 $O(m)$（因边数不超过原图边数）

综上，总时间复杂度为 $O(m \log n)$，可高效处理 $n \leq 1500$、$m$ 适中的数据范围。

总结

本题通过Dijkstra算法确定最短路径范围，筛选出公共有效边构建DAG，再用拓扑排序和动态规划求解最长公共路径，巧妙结合了最短路径与最长路径的求解思想，高效解决了问题。