Tourism

Masha lives in a country with $n$ cities numbered from $1$ to $n$. She lives in the city number $1$.

There is a direct train route between each pair of distinct cities $i$ and $j$, where $i \neq j$. In total there are $n(n-1)$ distinct routes. Every route has a cost, cost for route from $i$ to $j$ may be different from the cost of route from $j$ to $i$.

Masha wants to start her journey in city $1$, take exactly $k$ routes from one city to another and as a result return to the city $1$. Masha is really careful with money, so she wants the journey to be as cheap as possible. To do so Masha doesn’t mind visiting a city multiple times or even taking the same route multiple times.

Masha doesn’t want her journey to have odd cycles. Formally, if you can select visited by Masha city $v$, take odd number of routes used by Masha in her journey and return to the city $v$, such journey is considered unsuccessful.

Help Masha to find the cheapest (with minimal total cost of all taken routes) successful journey.Input

First line of input had two integer numbers $n,k$ ($2 \leq n \leq 80; 2 \leq k \leq 10$): number of cities in the country and number of routes in Masha’s journey. It is guaranteed that $k$ is even.

Next $n$ lines hold route descriptions: $j$-th number in $i$-th line represents the cost of route from $i$ to $j$ if $i \neq j$, and is 0 otherwise (there are no routes $i \to i$). All route costs are integers from $0$ to $10^8$.Output

Output a single integer — total cost of the cheapest Masha’s successful journey.Examplesinput

5 8
0 1 2 2 0
0 0 1 1 2
0 1 0 0 0
2 1 1 0 0
2 0 1 2 0

output

2

input

3 2
0 1 1
2 0 1
2 2 0

output

3

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
}
}
vector<vector<vector<pair<int, int>>>> inter(n);
for (int i = 0; i < n; i++) {
    inter[i].resize(n);
    for (int j = 0; j < n; j++) {
      for (int t = 0; t < n; t++) {
        if (i != t && t != j) {
          inter[i][j].emplace_back(a[i][t] + a[t][j], t);
        }
      }
      sort(inter[i][j].begin(), inter[i][j].end());
    }
  }
  vector<int> used(n, 0);
vector<int> seq(k / 2 + 1, -1);
seq[0] = seq[k / 2] = 0;
int cnt = 1;
used[0] = 1;
int ans = (int) 2e9;
function<void(int)> Dfs = [&](int v) {
if (v == k / 2) {
if (cnt == n) {
return;
}
int cur = 0;
for (int i = 0; 2 * i < k; i++) {
        for (auto& p : inter[seq[i]][seq[i + 1]]) {
          if (!used[p.second]) {
            cur += p.first;
            break;
          }
        }
      }
      ans = min(ans, cur);
      return;
    }
    for (int i = 0; i < n; i++) {
      cnt += !used[i];
      used[i] += 1;
      seq[v] = i;
      Dfs(v + 1);
      seq[v] = -1;
      used[i] -= 1;
      cnt -= !used[i];
    }
  };
  Dfs(1);
  cout << ans << '\n';
  return 0;
}