CF1310D Tourism

Masha 生活在一个有 $n$ 个城市的国家，这些城市编号从 $1$ 到 $n$。她住在编号为 $1$ 的城市。 在每一对不同的城市 $i$ 和 $j$ 之间（$i \neq j$）都有一条直达火车线路。总共有 $n(n-1)$ 条不同的线路。每条线路都有一个费用，从 $i$ 到 $j$ 的线路费用可能与从 $j$ 到 $i$ 的线路费用不同。 Masha 想从城市 $1$ 出发，恰好乘坐 $k$ 条线路，从一个城市到另一个城市，最终回到城市 $1$。Masha 非常节省，所以她希望旅程的总费用尽可能低。为此，Masha 不介意多次访问同一个城市，甚至多次乘坐同一条线路。 Masha 不希望她的旅程中包含奇环。具体来说，如果你可以选择 Masha 访问过的某个城市 $v$，经过奇数条她旅途中使用过的线路后又回到城市 $v$，这样的旅程被认为是不成功的。 请帮助 Masha 找到总费用最小的、成功的旅程（即不包含奇环的旅程）。

输入的第一行包含两个整数 $n, k$（$2 \leq n \leq 80; 2 \leq k \leq 10$）：表示国家中的城市数量和 Masha 旅程中的线路数量。保证 $k$ 是偶数。 接下来的 $n$ 行描述了每条线路的费用：第 $i$ 行的第 $j$ 个数字表示从 $i$ 到 $j$ 的线路费用（如果 $i \neq j$），如果 $i = j$，则为 $0$（不存在 $i \to i$ 的线路）。所有线路费用均为 $0$ 到 $10^8$ 之间的整数。

输出一个整数，表示 Masha 的最便宜的成功旅程的总费用。

由 ChatGPT 4.1 翻译