Preparando MOJI
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.
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 a single integer — total cost of the cheapest Masha's successful journey.
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
Informação
Provedor Codeforces
Código CF1310D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:59:37
Relacionados