嘿，这个问题确实戳中了常规图算法的痛点——当m达到1e9时，动态规划或者暴力遍历肯定直接歇菜，得用结合矩阵快速幂的最短路径变种方法，也就是基于Floyd-Warshall思想的矩阵乘法改造方案，下面给你详细拆解：

核心思路 #

我们的目标是找恰好走k = m-1条边的最短路径（可重复走边，任意起点/终点）。这里的关键是把“走k步的最短路径”转化为矩阵运算问题：

• 定义一个n×n的距离矩阵dist，其中dist[i][j]表示从顶点i到j走1步的最短路径长度（也就是原图的边权，因为是完全图，所有i≠j都有直接边；i==j初始设为无穷大，因为走1步没法留在原地，除非有自环，按题目给定处理）。
• 重新定义矩阵“乘法”：对于两个矩阵A和B，它们的“乘积”矩阵C满足：

  C[i][j] = min_{1≤k≤n} (A[i][k] + B[k][j])
  

  这个操作的本质是动态规划的状态转移：走a+b步从i到j的最短路径，等于先走a步到k，再走b步到j的所有可能中的最小值。
• 用快速幂计算dist的k次幂（用上面的自定义乘法），得到的矩阵就是所有顶点对走k步的最短路径长度。最后遍历这个矩阵的所有元素，取最小值就是答案（因为可以从任意起点出发）。

结合示例验证 #

拿你给的例子来说：n=3，m=5，所以k=4步。

1. 初始1步矩阵：

   dist[1][2] = 10, dist[1][3] = 100
   dist[2][1] = 10, dist[2][3] = 50
   dist[3][1] = 30, dist[3][2] = 70
   dist[i][i] = ∞（无自环）
   

2. 先算2步矩阵dist²：
   • dist²[1][1] = min(dist[1][2]+dist[2][1], dist[1][3]+dist[3][1]) = min(10+10, 100+30) = 20（对应路径1→2→1）
3. 再算4步矩阵dist⁴ = (dist²)²：
   • dist⁴[1][1] = min(dist²[1][1]+dist²[1][1], ...) = 20+20=40（对应路径1→2→1→2→1）
4. 遍历所有元素，最小值就是40，和示例答案一致。

具体实现步骤 #

1. 初始化矩阵：创建n×n的矩阵，填充初始边权，i==j设为无穷大（如果题目允许自环则按给定值）。
2. 自定义矩阵乘法：实现上述的min+加法规则的矩阵相乘函数。
3. 矩阵快速幂：用快速幂的思路计算dist的k次幂，初始的单位矩阵是：I[i][i]=0，I[i][j]=∞（i≠j），对应走0步的情况。
4. 取最小值：遍历结果矩阵的所有元素，最小的那个就是所求的最短路径长度。

复杂度分析 #

这个方法的时间复杂度是O(n³ log k)，其中n≤200，log2(1e9)≈30，总运算量约为200³×30=2.4×10^8，完全在可接受的范围内，不会超时。

内容的提问来源于stack exchange，提问作者noobgotbanned