Maximum-Product Simple Path in a Complete Directed Graph

You are given a complete directed graph with n nodes labeled 0 through n - 1. For every ordered pair of distinct nodes (i, j), there is a directed edge from i to j with a positive weight w[i][j]. Weights are not necessarily symmetric (w[i][j] may differ from w[j][i]), and weights may be less than 1.

A simple path is a sequence of two or more distinct nodes v1 -> v2 -> ... -> vk (no node may appear more than once). The score of a simple path is the product of the weights of its edges:

$$\text{score} = \prod_{t=1}^{k-1} w[v_t][v_{t+1}]$$

Return the maximum score over all simple paths in the graph.

Important: because edge weights can be smaller than 1, extending a path can decrease its score. The optimal path may use any number of nodes from 2 up to n — it is not necessarily a Hamiltonian path. Both the best subset of nodes, their order, and where the path stops must be chosen.

Input

• n: the number of nodes.
• w: an n x n matrix of numbers. For i != j, w[i][j] > 0 is the weight of the edge from i to j. Diagonal entries w[i][i] are given as 0 and represent no edge (self-loops do not exist and must not be used).

Output

• A single number: the maximum product of edge weights over all simple paths. Answers within a relative or absolute error of 1e-6 of the correct value are accepted.

Constraints

• 2 <= n <= 15
• 0 < w[i][j] <= 100 for all i != j, given with at most 4 digits after the decimal point
• w[i][i] = 0 for all i

Example 1

n = 3
w = [
 [0, 2.0, 0.5],
 [1.5, 0, 4.0],
 [0.25, 3.0, 0 ]
]

Output: 8.0

The path 0 -> 1 -> 2 has score 2.0 * 4.0 = 8.0. No other simple path scores higher (e.g., 2 -> 1 -> 0 scores 3.0 * 1.5 = 4.5, and extending 0 -> 1 -> 2 is impossible since all three nodes are already used).

Example 2

n = 3
w = [
 [0, 5.0, 0.1],
 [0.2, 0, 0.3],
 [0.4, 0.6, 0 ]
]

Output: 5.0

The two-node path 0 -> 1 scores 5.0. Every extension multiplies by a weight below 1 and lowers the score (e.g., 0 -> 1 -> 2 scores 5.0 * 0.3 = 1.5), so stopping early is optimal.

Example 3

n = 2
w = [
 [0, 0.5],
 [0.9, 0 ]
]

Output: 0.9

The only simple paths are 0 -> 1 (score 0.5) and 1 -> 0 (score 0.9).