Submission #67638408

---

Source Code Expand

<?php

declare(strict_types=1);

/**
 * 距離行列を計算する
 *
 * @param array<int, array{int, int}> $coords 各都市の座標 [(x1, y1), ..., (xN, yN)]
 * @return array<int, array<int, float>> 距離行列 dist[i][j] = 都市iからjへの距離
 */
function computeDistances(array $coords): array {
    $N = count($coords);
    $dist = array_fill(0, $N, array_fill(0, $N, 0.0));
    for ($i = 0; $i < $N; $i++) {
        for ($j = 0; $j < $N; $j++) {
            $dx = $coords[$i][0] - $coords[$j][0];
            $dy = $coords[$i][1] - $coords[$j][1];
            $dist[$i][$j] = hypot($dx, $dy);
        }
    }
    return $dist;
}

/**
 * 巡回セールスマン問題を解く
 *
 * @param int $N 都市の数 (2 <= N <= 15)
 * @param array<int, array{int, int}> $coords 各都市の座標
 * @return float 最短距離（誤差1e-3以内）
 */
function solveTSP(int $N, array $coords): float {
    $dist = computeDistances($coords);
    $INF = INF;

    // dp[s][u] := 訪問済み集合s, 現在地u のときの最短距離
    $dp = array_fill(0, 1 << $N, array_fill(0, $N, $INF));
    $dp[1][0] = 0.0;

    for ($s = 1; $s < (1 << $N); $s++) {
        for ($u = 0; $u < $N; $u++) {
            if (!(($s >> $u) & 1)) continue;
            for ($v = 0; $v < $N; $v++) {
                if (($s >> $v) & 1) continue;
                $ns = $s | (1 << $v);
                $dp[$ns][$v] = min($dp[$ns][$v], $dp[$s][$u] + $dist[$u][$v]);
            }
        }
    }

    $res = $INF;
    for ($u = 1; $u < $N; $u++) {
        $res = min($res, $dp[(1 << $N) - 1][$u] + $dist[$u][0]);
    }

    return $res;
}

/**
 * 標準入力から座標情報を読み取り、solveTSP を呼び出すメイン関数
 */
function main(): void {
    [$N] = sscanf(trim(fgets(STDIN)), "%d");
    $coords = [];

    for ($i = 0; $i < $N; $i++) {
        [$x, $y] = sscanf(trim(fgets(STDIN)), "%d %d");
        $coords[] = [$x, $y];
    }

    $result = solveTSP($N, $coords);

    // 小数点以下12桁で出力（誤差1e-3対策）
    printf("%.12f\n", $result);
}

main();

Submission Info

Judge Result