import numpy as np

def tsp_dp(distances):
    n = len(distances)
    dp = np.full((1 << n, n), np.inf)
    path = np.zeros((1 << n, n), dtype=int)

    for i in range(n):
        dp[1 << i][i] = 0

    for S in range(1, 1 << n):
        for j in range(n):
            if not (S & (1 << j)):
                continue
            for k in range(n):
                if k == j or not (S & (1 << k)):
                    continue
                if dp[S][j] > dp[S - (1 << j)][k] + distances[k][j]:
                    dp[S][j] = dp[S - (1 << j)][k] + distances[k][j]
                    path[S][j] = k

    final_path = []
    S = (1 << n) - 1
    j = 0
    while S:
        final_path.append(j)
        k = path[S][j]
        S -= 1 << j
        j = k
    final_path.append(0)

    ans = float('inf')
    for j in range(n):  # 枚举所有结束点
        if distances[j][0] != np.inf:  # 如果结束点j与起点0相连
            ans = min(ans, dp[(1 << n) - 1][j] + distances[j][0])

    return ans, final_path
# 示例使用
distances = np.array([
    [np.inf, 50, 99, np.inf, 64, np.inf],
    [50, np.inf, 12, 45, 74, 13],
    [99, 12, np.inf, 25, np.inf, 61],
    [np.inf, 45, 25, np.inf, 45, 47],
    [64, 74, np.inf, 45, np.inf, np.inf],
    [np.inf, 13, 61, 47, np.inf, np.inf]
])
min_cost, min_path = tsp_dp(distances)
print("Minimum cost:", min_cost)
print("Minimum path:", min_path)