Миша живет в стране, в которой есть $$$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$$$ строках записано описание стоимостей маршрутов, $$$j$$$-е число в $$$i$$$-й строке равно стоимости маршрута из города $$$i$$$ в город $$$j$$$, если $$$i \neq j$$$, иначе число равно нулю (маршрутов $$$i \to i$$$ нет). Все стоимости маршрутов — целые числа от $$$0$$$ до $$$10^8$$$.
Выведите одно целое число: минимальная сумма стоимостей маршрутов в удачном путешествии.
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
2
3 2 0 1 1 2 0 1 2 2 0
3
Название |
---|