407305: GYM102759 C Economic One-way Roads

The country of RUN has $$$N$$$ cities, some of which are connected by two-way roads. Each road connects two different cities, and no two roads connect the same pair of cities. It is not guaranteed that every city is reachable from every other city by traveling along some roads.

Due to traffic issues, the mayor of RUN decided to make all roads one-way. After doing so, it must be possible to move from any city to any other city using one or more roads. To save as much money as possible, over all possible road orientations that satisfy this condition, the mayor will pick the cheapest one. Note that the cost of orienting a road depends on both the specific road and the direction it is oriented in.

On the first line, the number of cities $$$2 \leq N \leq 18$$$ is given.

On each of the next $$$N$$$ lines, $$$N$$$ space-separated integers are given. The $$$j$$$-th integer in the $$$i+1$$$-th line, $$$a_{ij}$$$, is the cost of orienting the road from city $$$i$$$ to $$$j$$$, or $$$-1$$$ if there is no road connecting these two cities.

For all integers $$$1 \leq i \leq N$$$, $$$a_{ii} = -1$$$. For all pairs of distinct integers $$$1 \leq i, j \leq N$$$, either $$$a_{ij} = a_{ji} = -1$$$ or $$$0 \leq a_{ij}, a_{ji} \leq 10^6$$$.

Output the minimum cost needed to orient all roads to satisfy the mayor's condition. If it is impossible, output -1.

4
-1 3 2 -1
3 -1 7 7
5 9 -1 9
-1 6 7 -1

27

6
-1 1 2 -1 -1 -1
3 -1 4 -1 -1 -1
5 6 -1 0 -1 -1
-1 -1 0 -1 6 5
-1 -1 -1 4 -1 3
-1 -1 -1 2 1 -1

-1

For the first sample, this is the cheapest way to orient the roads to satisfy the mayor's condition: