← 返回题目列表

Codeforces · 1310/D

D. 旅游

中文机器翻译题面 查看原题

玛莎生活在一个拥有 $$$n$$$ 城市的国家,城市编号从 $$$1$$$ 到 $$$n$$$。她住在城市号$$$1$$$。

每对不同城市 $$$i$$$ 和 $$$j$$$ 之间都有直达火车路线,其中 $$$i \neq j$$$。总共有 $$$n(n-1)$$$ 条不同的路线。每条路线都有一个成本,从 $$$i$$$ 到 $$$j$$$ 的路线成本可能与从 $$$j$$$ 到 $$$i$$$ 的路线成本不同。

玛莎想要在 $$$1$$$ 城市开始她的旅程,从一个城市到另一个城市正好采取 $$$k$$$ 路线,然后返回 $$$1$$$ 城市。玛莎在花钱方面非常谨慎,所以她希望旅程尽可能便宜。为此,玛莎不介意多次访问一座城市,甚至多次走同一条路线。

玛莎不希望她的旅程有奇怪的循环。正式来说,如果您可以选择访问玛莎城市$$$v$$$,并选择玛莎旅途中使用的奇数条路线并返回城市$$$v$$$,则该旅程被视为不成功。

帮助玛莎找到最便宜(所有路线总成本最小)的成功旅程。

输入

输入的第一行有两个整数 $$$n,k$$$ ($$$2 \leq n \leq 80; 2 \leq k \leq 10$$$):该国的城市数量和玛莎旅程中的路线数量。保证 $$$k$$$ 是偶数。

接下来的 $$$n$$$ 行保存路线描述:$$$i$$$ 行中的第 $$$j$$$ 数字表示如果 $$$i \neq j$$$ 则从 $$$i$$$ 到 $$$j$$$ 的路线成本,否则为 0(没有路线 $$$i \to i$$$)。所有路线成本均为从 $$$0$$$ 到 $$$10^8$$$ 的整数。

输出

输出一个整数——最便宜的玛莎成功旅程的总成本。

示例

输入 #1

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

输出 #1

2

输入 #2

3 2
0 1 1
2 0 1
2 2 0

输出 #2

3