難しい 1件解決済み 正答率100.0%

Shortest Delivery Tour

Visit every city once and return home as cheaply as possible.

このチャレンジで学べること

  • 訪問済みの都市をビットで保存する
  • 部分集合と最後の都市に対する DP を書く
  • 小さな TSP を厳密に解く

問題

A courier starts at city 0, visits every other city exactly once and returns to city 0. distances[i][j] is the cost from i to j. With at most 15 cities, a bitmask dynamic program (Held–Karp) over visited sets is fast enough.

Implement shortest_tour(distances).

Input

distances: An n × n matrix of travel costs; distances[i][i] = 0.

Output

Return the cost of the cheapest round trip.

制約

1 ≤ n ≤ 15; 0 ≤ cost ≤ 1,000,000

例

例 1
入力:
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

期待される出力:
expected = 80
入力:
std::vector<std::vector<long long>> distances = {
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};

期待される出力:
long long expected = 80;
入力:
long[][] distances = new long[][] {
    new long[] {0, 10, 15, 20},
    new long[] {10, 0, 35, 25},
    new long[] {15, 35, 0, 30},
    new long[] {20, 25, 30, 0}
};

期待される出力:
long expected = 80;

解説

0→1→3→2→0 costs 10 + 25 + 30 + 15 = 80, the cheapest tour.

例 2
入力:
distances = [
    [0]
]

期待される出力:
expected = 0
入力:
std::vector<std::vector<long long>> distances = {
    {0}
};

期待される出力:
long long expected = 0;
入力:
long[][] distances = new long[][] {
    new long[] {0}
};

期待される出力:
long expected = 0;

解説

With one city there is nowhere to go: 0.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

都市数が少ないなら、全ルートを列挙する代わりに、どの都市を訪問済みかを追跡しよう。

ヒント 2

都市の部分集合に対するDPを使い、その集合で各都市に到達する最小コストを覚える。

ヒント 3

city 0 から始めて city 0 に戻ること、そして非常に高コストでも有効な経路がある場合をきちんと扱うことに注意。

目安の計算量

時間 O(n^2 2^n)、追加メモリ O(n 2^n)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 837 ms - 5/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。