P10447 Shortest Hamilton Path

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.

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 one integer, the length of the shortest Hamilton path.

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