Sightseeing Tour
Time limit8sMemory limit512 MB
Orient every edge of a complete undirected graph at minimum cost so that the resulting digraph has a Hamiltonian path visiting all N areas.
- Level
Medium6 of 10
- Topics
- Graph, Dynamic programming, Bit manipulation, Greedy
- Solved
- No attempts yet
Problem
KM city has N sightseeing areas. Currently every pair of areas is connected by a bidirectional road.
For some reason, Mr. KM, the mayor of this city, decided to make all of these roads one-way. It costs Ci,j dollars to renovate the road between area i and area j into a one-way road from area i to area j. Mr. KM is economical, so he wants to minimize the total cost of the renovation.
Tourism is the most important industry for KM city, so there must exist a tour that goes through all the sightseeing areas, visiting each area exactly once. The first and last areas of the tour need not be the same. Given this situation, can you calculate the minimum total cost required for the renovation?
Input
The first line contains the number of sightseeing areas N (1 ≤ N ≤ 100). The next N lines describe the integer matrix C, where the j-th element of the i-th row is Ci,j (0 ≤ Ci,j ≤ 1, 000, 000). For each i, Ci,i is always zero.
Output
Print the minimum cost on one line.