Tourism (Codeforces 1314D)
Tags: DP, probabilities

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.


Sample Inputs:
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

3 2
0 1 1
2 0 1
2 2 0

Sample Outputs:
2

3

Solution (Python):
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
pow2 = [1]
for _ in range(30):
    pow2.append(2 * pow2[-1])
inf = pow(10, 9) + 1
ans = inf
for _ in range(5000):
    u = [random.randint(0, pow(2, 30) - 1) for _ in range(3)]
    x = [[] for _ in range(2)]
    for i in range(n):
        x[min(1, u[i // 30] & pow2[i % 30])].append(i)
    d = [[] for _ in range(n)]
    (x1, x2) = x
    for _ in range(2):
        for i in x1:
            ai = a[i]
            for j in x2:
                d[i].append((j, ai[j]))
        (x1, x2) = (x2, x1)
    dp0 = [inf] * n
    dp0[0] = 0
    for _ in range(k):
        dp = [inf] * n
        for i in range(n):
            dpi = dp0[i]
            for (j, d0) in d[i]:
                dp[j] = min(dp[j], dpi + d0)
        if min(dp0) > ans:
            break
        dp0 = dp
    ans = min(ans, dp[0])
print(ans)

Solution (Python):
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
pow2 = [1]
for _ in range(30):
    pow2.append(2 * pow2[-1])
inf = pow(10, 9) + 1
ans = inf
for _ in range(10000):
    u = [random.randint(0, pow(2, 30) - 1) for _ in range(3)]
    x = [[] for _ in range(2)]
    for i in range(n):
        x[min(1, u[i // 30] & pow2[i % 30])].append(i)
    d = [[] for _ in range(n)]
    (x1, x2) = x
    for _ in range(2):
        for i in x1:
            ai = a[i]
            for j in x2:
                d[i].append((j, ai[j]))
        (x1, x2) = (x2, x1)
    dp0 = [inf] * n
    dp0[0] = 0
    for _ in range(k):
        dp = [inf] * n
        for i in range(n):
            dpi = dp0[i]
            for (j, d0) in d[i]:
                dp[j] = min(dp[j], dpi + d0)
        if min(dp0) > ans:
            break
        dp0 = dp
    ans = min(ans, dp[0])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from random import randint
(n, T) = map(int, input().split())
COST = [list(map(int, input().split())) for i in range(n)]
ANS = 1 << 30
for tests in range(5 * 10 ** 3):
    COLOR = [randint(0, 1) for i in range(n)]
    COLOR[0] = 0
    DP = [1 << 30] * n
    DP[0] = 0
    for trip in range(T):
        NDP = [1 << 30] * n
        if trip % 2 == 0:
            for j in range(n):
                if COLOR[j] == 1:
                    continue
                for k in range(n):
                    if j != k and COLOR[k] == 1:
                        NDP[k] = min(NDP[k], DP[j] + COST[j][k])
        else:
            for j in range(n):
                if COLOR[j] == 0:
                    continue
                for k in range(n):
                    if j != k and COLOR[k] == 0:
                        NDP[k] = min(NDP[k], DP[j] + COST[j][k])
        DP = NDP
    ANS = min(ANS, DP[0])
print(ANS)