日期：2026年11月7日
ZeroJudge 題目連結：s111.C. Bitonic Path
解題想法
題目給一個整數 $n ~(2 \leq n \leq 2000)$，代表共有 $n$ 個點，編號為 $1$ 到 $n$。接下來 $n$ 列，每列有兩個整數 $x_i, y_i ~(-10000 \leq x_i, y_i \leq 10000)$，代表第 $i$ 個點的坐標，測資保證這些坐標依照 $x$ 由小到大排序。要找出一條路徑長最短的路徑，且從節點 $1$ 走到節點 $n$ 時 $x$ 坐標遞增，從節點 $n$ 走回節點 $1$ 時 $x$ 坐標遞減，除了節點 $1$ 以外，其它節點只能走到一次。
由於這題的 $n$ 很大，需要用二維 DP 才不會超時。題目雖然看起來是要來回各走一趟，實際上就是要找到兩點從節點 $1$ 走到節點 $n$ 且中途節點不重複的路徑，並使路徑長最短。以下解題時將節點編號改成 $0$ 到 $n-1$。將節點坐標存到 $pos$ 之中。我們可以假想有兩個人從節點 $0$ 出發，速度較快的人停留在節點 $i$，速度較慢的人停留在節點 $j$，且 $i > j$，這樣兩個人走的路徑中途的節就不會重複。定義一個 $n \times n$ 的二維陣列 $dp$，$dp[i][j]$ 代表速度較快的人停留在節點 $i$，速度較慢的人停留在節點 $j$ 時，對應的最短路徑長，初始值皆設為超出題目上限的值。並初始化為 $dp[0][0] = 0$，因為第一步一定是較快的人從節點 $0$ 走到 $1$，因此 $dp[1][0] = dist(pos[1] - pos[0])$。
接下來用雙層 for 迴圈更新 $dp$。外層迴圈測試較快的人停留在節點 $i = 1$ 到 $i = n-2$，內層迴圈測試較慢的人停留在節點 $j = 0$ 到 $j = i-1$。更新時有兩種可能性：
- 快的人從 $i$ 走到 $i+1$，慢的人待在 $j$。
- 慢的人從 $j$ 走到 $i+1$，快、慢交換，慢的待在 $i$。
Python 程式碼
Python 寫 2 維 DP 還是會超時，需要壓扁成 1 維 DP。
def solve():
import sys
from math import hypot # 計算兩點距離
def dist(a, b):
return hypot(a[0] - b[0], a[1] - b[1])
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
n = int(data[ptr]) # n 個點
ptr += 1
# 讀取 n 個點的坐標，測資已經依照 x 由小到大排序
pos = []
for _ in range(n):
x = int(data[ptr])
y = int(data[ptr + 1])
ptr += 2
pos.append((x, y))
# 用 2維 DP 找最短路徑長，dp[i][j] 代表快的人在 i、慢的人在 j 的最短路徑長，預設為無窮大
dp = [[float('inf')] * n for _ in range(n)]
dp[0][0] = 0 # 起點
dp[1][0] = dist(pos[1], pos[0])
for i in range(1, n-1):
for j in range(0, i):
# 狀況1，快的人從 i 走到 i+1，慢的人待在 j
dp[i+1][j] = min(dp[i+1][j], dp[i][j] + dist(pos[i+1], pos[i]))
# 狀況2，慢的人從 j 走到 i+1，快、慢交換，慢的待在 i
dp[i+1][i] = min(dp[i+1][i], dp[i][j] + dist(pos[i+1], pos[j]))
# 快的人已經走到 n-1，慢的人從 j 走到 n-1
for j in range(n):
dp[n-1][n-1] = min(dp[n-1][n-1], dp[n-1][j] + dist(pos[n-1], pos[j]))
# 印出結果
result.append(f"{dp[n-1][n-1]:.2f}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
