NP-hard

The travelling salesman problem is NP-hard, so no fast method is known once the number of cities grows. Here you solve a variant that adds one rule about the visiting order.

The cities are numbered $1$ to $N$, and the travel time between every pair of cities is given. Visit every city exactly once and make the total travel time as small as possible.

The rule is this. When you visit city $K$, every city with a smaller number is visited before city $K$, or every one of them is visited after city $K$. Placing one city smaller than $K$ before city $K$ and another one after it is not allowed.

You may start at any city and finish at any city. Only the times between neighbouring cities in the visiting order are added up, and the trip back from the last city to the first one is not counted.

Write a program that finds the smallest total time of a visiting order that obeys the rule.

The first line has the number of cities $N$. ($2 \le N \le 1500$)

Each of the next $N$ lines has $N$ integers. The $B$-th number on the $A$-th line is the time needed to go from city $A$ to city $B$, and it equals the $A$-th number on the $B$-th line. It is $0$ when $A$ and $B$ are the same, and an integer between $1$ and $1000$ otherwise.

Print the smallest total time needed to visit every city while obeying the rule.

Take the order $1, 3, 2$ with $N = 3$. The cities numbered below $3$ are $1$ and $2$, city $1$ sits before city $3$, and city $2$ sits after it, so this order breaks the rule. With $N = 3$ only four orders obey it: $(1, 2, 3)$, $(3, 2, 1)$, $(2, 1, 3)$, $(3, 1, 2)$.