import numpy as np


def dfs_tsp(graph, start, current, path, visited, cost, min_cost, min_path):
    if len(path) == len(graph) and graph[current][start] != np.inf:
        path.append(start)
        cost += graph[current][start]
        if cost < min_cost[0]:
            min_cost[0] = cost
            min_path[0] = path.copy()
        path.pop()
        cost -= graph[current][start]
        return

    for next_node in range(len(graph)):
        if graph[current][next_node] != np.inf and not visited[next_node]:
            visited[next_node] = True
            path.append(next_node)
            cost += graph[current][next_node]
            dfs_tsp(graph, start, next_node, path, visited, cost, min_cost, min_path)
            visited[next_node] = False
            path.pop()
            cost -= graph[current][next_node]


def tsp_dfs(graph):
    n = len(graph)
    min_cost = [float('inf')]
    min_path = [[]]

    for start_node in range(n):
        visited = [False] * n
        path = [start_node]
        cost = 0
        visited[start_node] = True
        dfs_tsp(graph, start_node, start_node, path, visited, cost, min_cost, min_path)

    return min_cost[0], min_path[0]


# 示例使用
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_dfs(distances)
print("Minimum cost:", min_cost)
print("Minimum path:", min_path)