20007. Fast Travelling Salesman Problem

I'm a slow walker, but I never walk backwards.

Task Description

給一組城市和每一個城市之間的距離,請找出從起點城市出發,經過所有城市且不重複回到起點城市的最短距離和。

例如,走訪順序為 $1-2-4-3-1$. 距離總和為 $10+25+30+15 = 80$.

p10139.

Subtask

$N \le 100$

Input Format

只有一組測資,每組第一行有一個整數 $N$,表示有 $N$ 座城市,接下來會有 $N$ 行,每行上有 $N$ 個非負整數 $D_{i, j}$ 表示節點 $i$ 到節點 $j$ 的距離,如果 $D_{i, j} = 0$,視同沒有邊。

你可以假設每一條邊可能是單向的,保證至少一條 TSP 路徑。

  • $3 \lt N \leq 100$
  • $0 \lt \textit{distance between any pair of cities} \le 10000$

Output Format

輸出一行最小距離和。

Sample Input 1

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Sample Output 1

80

Discussion