| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB | 44 | 14 | 10 | 30.303% |
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
For the first sample, this is the cheapest way to orient the roads to satisfy the mayor's condition:
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
University > KAIST > KAIST ICPC Mock Competition > 2020 KAIST 10th ICPC Mock Competition C번
Contest > Open Cup > 2020/2021 Season > Stage 3: Grand Prix of Korea C번