都市 \(2\) ～都市 \(N\) を訪問する順序を全探索します。そのような場合の数は \((N-1)!\) 通りであり、各場合について、移動時間の合計の計算に \(O(N)\) かかるので、全体で \(O(N!)\) 時間で問題を解くことができます。都市 \(1\) からスタートし、都市 \(1\) に戻ってくるという条件に注意してください。

都市 \(2\) ～ 都市 \(N\) を訪問する順序の全探索は、C++ならnext_permutation、Python なら itertools.permutations などを用いて行うことができます。C や Java には順列の全列挙を行う標準関数はないため、自分で適切に実装する必要があります。

回答例(C++)

回答例(Python)

回答例(C)