Problem Description

Given a weighted undirected graph with $n$ vertices, numbered from $0$ to $n-1$, find the shortest Hamilton path from the start vertex $0$ to the end vertex $n-1$.

A Hamilton path here is defined as a path from $0$ to $n-1$ that visits every vertex exactly once, with no repeats and no omissions.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain $n$ integers. The $j$-th integer in the $i$-th line represents the distance from vertex $i-1$ to vertex $j-1$ (denoted as $a[i-1,j-1]$).

For any $x,y,z$, the testdata guarantees that $a[x,x]=0$, $a[x,y]=a[y,x]$, and $a[x,y]+a[y,z] \ge a[x,z]$.

Output Format

Output one integer, the length of the shortest Hamilton path.

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

18

Hint

Constraints: for all testdata, $1 \le n \le 20$, and $0 \le a[i,j] \le 10^7$.

Translated by ChatGPT 5