Fifteen Stops, One-Way Streets

A night bus leaves the depot (stop 0), visits every other stop exactly once and comes back to the depot. The old town is full of one-way streets, so driving from i to j can take a different time from driving back, and some direct trips are impossible.

t[i][j] is the driving time from stop i directly to stop j, or -1 if there is no direct street in that direction. t[i][i] is always 0. Write fastest_loop(t) that returns the smallest total driving time of such a closed loop, or -1 if no loop is possible. With a single stop the answer is 0.

With 15 stops there are 14! (more than 87 billion) orders, so trying them all will not finish.

The larger tests build their tables with drive_times(n, seed, closed), which is available in your code: about the share closed of the direct trips are -1.

Examples

Input:  t = [[0, 3, 8, 5],
             [9, 0, 2, 7],
             [4, 6, 0, 3],
             [1, 8, 5, 0]]
Output: 9
Explanation: 0 -> 1 -> 2 -> 3 -> 0 takes 3 + 2 + 3 + 1 = 9.
             The same loop driven backwards, 0 -> 3 -> 2 -> 1 -> 0, takes 5 + 5 + 6 + 9 = 25.

Input:  t = [[0, -1, 4],
             [2, 0, -1],
             [-1, 5, 0]]
Output: 11
Explanation: 0 -> 1 is closed, so the only loop is 0 -> 2 -> 1 -> 0: 4 + 5 + 2.

Input:  t = [[0, -1],
             [3, 0]]
Output: -1

Constraints

• 1 <= n <= 15, t is an n × n list of lists
• t[i][i] == 0; every other entry is -1 or an integer from 1 to 10**4

Goals

• Replace an exhaustive search over orders by a DP over (visited set, last stop)
• Handle asymmetric costs and missing connections
• Estimate the size of a state space before writing the search