349删除路径后的最短路问题

问题描述

小 F 正在探索一个有 n 个点的地图，其中每个点都有对应的二维坐标 (xi, yi)。起点是第 s 个点，终点是第 t 个点，原本所有点之间都有一条线段，表示可以通行，并且长度为欧几里得距离。但是由于某些意外，起点 s 和终点 t 之间的直接通行路径被删除了。小 F 希望你帮忙计算从 s 到 t 的最短路径，允许经过其他点，但不能直接通过删除的那条线。

需要注意的是，点 i, j 之间的欧几里得距离计算公式为：

[ \text{distance} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} ]

你需要输出从起点 s 到终点 t 的最短距离，结果需要四舍五入到小数点后两位。

题解

我们需要计算从起点 s 到终点 t 的最短路径，允许经过其他点，但不能直接通过删除的那条线。由于任意两个点之间都有线段连接，可以通过枚举中间点来计算最短距离

代码实现

def solution(n: int, s: int, t: int, x: list, y: list) -> str:
    s -= 1
    t -= 1
    from math import sqrt

    def dis(p, q):
        dx = x[p] - x[q]
        dy = y[p] - y[q]
        return sqrt(dx * dx + dy * dy)

    res = min(dis(s, i) + dis(t, i) for i in range(n) if i != s and i != t)
    return f"{res:.2f}"

if __name__ == '__main__':
    print(solution(n=5, s=1, t=5, x=[17253, 25501, 28676, 30711, 18651], y=[15901, 15698, 32041, 11015, 9733]) == '17333.65')
    print(solution(n=4, s=2, t=4, x=[5000, 12000, 8000, 14000], y=[3000, 9000, 1000, 4000]) == '15652.48')
    print(solution(n=6, s=3, t=6, x=[20000, 22000, 24000, 26000, 28000, 30000], y=[15000, 13000, 11000, 17000, 19000, 21000]) == '11772.70')

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是点的数量。我们需要遍历所有点来计算最短路径。
空间复杂度：$O(1)$。