題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 P1027 [NOIP 2001 提高组] Car 的旅行路线

Problem Statement

題目簡述

有 $S$ 個城市，每個城市有 $4$ 個機場，分別位於某個矩形的四個頂點，但輸入只給出其中 $3$ 個機場座標，需要先還原第 $4$ 個機場。同城機場間可搭高速鐵路，單位里程花費為該城市的 $T_i$ ；異城機場間可搭航線，單位里程花費統一為 $t$ 。求從城市 $A$ 任一機場到城市 $B$ 任一機場的最小花費。

Constraints

約束條件

測試資料組數 $1\le t \le 10$
城市數 $1\le S \le 100$
$1\le A,B \le S$
所有座標為正整數

思路：計算幾何 + 多源最短路

題型定位

本題是多源最短路的建模題。核心不在最短路演算法本身，而在如何將「矩形城市 + 機場」的題面轉化為一張帶權圖。

核心套路

給定矩形三頂點求第四點 $\rightarrow$ 建圖 $\rightarrow$ Floyd–Warshall（或多次 Dijkstra）。

第一步：從三個點還原矩形第四點

每個城市給出三個機場座標。矩形的一個關鍵性質：三個點構成一個直角三角形，直角頂點是矩形的一個角，另外兩點是對角線的兩端。

如何找出直角頂點？計算三點兩兩之間的距離平方。若

d_{AB}^2 = d_{AC}^2 + d_{BC}^2

則 $C$ 是直角頂點， $A,B$ 是對角線的兩端（ $AB$ 是斜邊）。

知道對角線兩端和直角頂點後，利用矩形對角線中點重合的性質：

(x_4, y_4) = (x_{\text{對角1}} + x_{\text{對角2}} - x_{\text{直角}},\ y_{\text{對角1}} + y_{\text{對角2}} - y_{\text{直角}})

原理

矩形的對角線互相平分，因此對角線兩端點的座標和等於另外兩端點的座標和。由此推出 $x_4 = x_a + x_b - x_c$ 。

第二步：建圖

將每個城市的 $4$ 個機場視為圖中的節點，總共 $m = 4S$ 個節點。城市 $i$ 的四個機場編號為 $4i, 4i+1, 4i+2, 4i+3$ 。

邊有兩類，均為雙向：

城市內：同一城市中任兩機場間有高速鐵路，邊權為 $\text{歐氏距離} \times T_i$ 。
城市間：不同城市的任兩機場間有航線，邊權為 $\text{歐氏距離} \times t$ 。

注意

城市內鐵路和城市間航線的單位里程價格不同——鐵路用各城市自己的 $T_i$ ，航線統一用 $t$ 。建邊時切勿混淆。

由於 $S \le 100$ ， $m \le 400$ ，總邊數不超過 $m^2 \approx 1.6\times 10^5$ ，完全可行。

第三步：求多源最短路

起點城市 $A$ 有 $4$ 個機場可選，終點城市 $B$ 也有 $4$ 個機場可選。這是一個多源到多匯的最短路問題。

兩種做法：

從起點的 $4$ 個機場各跑一次 Dijkstra，取到達終點 $4$ 個機場的最小值。
直接跑 Floyd–Warshall，最後枚舉 $4 \times 4$ 對起終點取最小值。

由於 $m \le 400$ ，Floyd–Warshall 的 $\mathcal{O}(m^3)$ 約為 $6.4 \times 10^7$ 次運算，Python 可通過。Floyd 實作更簡潔，故採用之。

Floyd 常數優化

內層迴圈中，若起點到中繼點已經不可達（ $g[i][k] = \infty$ ），可以直接跳過該 $j$ 迴圈，避免無效的比較與賦值。

第四步：取答案

城市編號轉為 $0$ -indexed（即 $A-1$ 和 $B-1$ ）。答案為：

\min_{0 \le i,j \le 3} g[(A-1)\times 4 + i][(B-1)\times 4 + j]

本題要點

矩形三點求第四點：畢氏定理找直角頂點，再以對角線中點公式求第四點。
多源多匯最短路：將起終點各自拆成多個節點，最後枚舉配對取最小值。
建圖時注意區分城市內鐵路單價 $T_i$ 和城市間航線單價 $t$ 。

複雜度分析

時間複雜度： $\mathcal{O}(S^3)$ ，其中 $m = 4S \le 400$ ，Floyd 為 $\mathcal{O}(m^3)$
空間複雜度： $\mathcal{O}(S^2)$ ，用於鄰接矩陣

Code

def dist(x1, y1, x2, y2):
    """歐氏距離"""
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def dist2(x1, y1, x2, y2):
    """歐氏距離平方（用於比較邊長，避免浮點誤差）"""
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

class City:
    def __init__(self, data: list[int]):
        x1, y1, x2, y2, x3, y3, price = data
        # 還原矩形第四點
        self.points = [(x1, y1), (x2, y2), (x3, y3),
                       self.get_last_point(x1, y1, x2, y2, x3, y3)]
        self.price = price  # 城市內鐵路單位里程價格 T_i

    @staticmethod
    def get_last_point(x1, y1, x2, y2, x3, y3):
        """給定矩形三頂點，求第四頂點。

        利用畢氏定理找出直角頂點：直角頂點滿足其到另外兩點的
        距離平方和等於另外兩點間的距離平方。知道直角頂點後，
        第四點 = 對角線兩端和 - 直角頂點。
        """
        ab = dist2(x1, y1, x2, y2)
        ac = dist2(x1, y1, x3, y3)
        bc = dist2(x2, y2, x3, y3)
        if ab == ac + bc:
            # 點 3 是直角頂點（ab 為斜邊），點 1,2 是對角線兩端
            return x1 + x2 - x3, y1 + y2 - y3
        elif ac == ab + bc:
            # 點 2 是直角頂點（ac 為斜邊），點 1,3 是對角線兩端
            return x1 + x3 - x2, y1 + y3 - y2
        else:  # bc == ab + ac
            # 點 1 是直角頂點（bc 為斜邊），點 2,3 是對角線兩端
            return x2 + x3 - x1, y2 + y3 - y1

t = int(input())  # 測試資料組數

for _ in range(t):
    n, price, A, B = map(int, input().split())  # n = S（城市數），price = t（航線單價）
    citys = [City(list(map(int, input().split()))) for _ in range(n)]

    m = n * 4  # 總節點數 = 城市數 × 4
    g = [[float('inf')] * m for _ in range(m)]

    # --- 建圖：城市內鐵路 ---
    for k, city in enumerate(citys):
        for i, p1 in enumerate(city.points):
            for j, p2 in enumerate(city.points):
                g[k * 4 + i][k * 4 + j] = dist(p1[0], p1[1], p2[0], p2[1]) * city.price

    # --- 建圖：城市間航線 ---
    for i, city1 in enumerate(citys):
        for j, city2 in enumerate(citys):
            if i == j:
                continue
            for k1, p1 in enumerate(city1.points):
                for k2, p2 in enumerate(city2.points):
                    g[i * 4 + k1][j * 4 + k2] = dist(p1[0], p1[1], p2[0], p2[1]) * price

    # --- Floyd–Warshall 求全源最短路 ---
    for k in range(m):
        for i in range(m):
            if g[i][k] == float('inf'):
                continue  # 跳過不可達的中繼點，常數優化
            for j in range(m):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

    # --- 取答案：枚舉起終點機場的 4×4 種配對 ---
    A -= 1
    B -= 1
    ans = float('inf')
    for i in range(4):
        for j in range(4):
            ans = min(ans, g[A * 4 + i][B * 4 + j])
    print(f'{ans:.1f}')