经典算法（四）旅行商问题

import sys

# 冲突检测
def conflict(k):
    global n, graph, x, min_cost
    # 第k个节点，是否前面已经走过
    if k < n and x[k] in x[:k]:
        return True
    # 回到出发节点
    if k == n and x[k] != x[0]:
        return True
    # 前面部分解的旅费之和超出已经找到的最小总旅费
    cost = sum([graph[node1][node2] for node1, node2 in zip(x[:k], x[1:k+1])])
    if 0 < min_cost < cost:
        return True
    return False

# 旅行商问题（TSP）
def tsp(k): # 到达（解x的）第k个节点
    global n, graph, x, min_cost
    if k > n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n）
        cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])])# 计算总旅费
        if min_cost == 0 or cost < min_cost:
            min_cost = cost
    else:
        for node in graph[x[k-1]]:# 遍历节点x[k-1]的邻接节点（状态空间）
            x[k] = node
            if not conflict(k):
                tsp(k+1)



if __name__ == "__main__":
    n = int(sys.stdin.readline().strip()) # 节点数
    m = int(sys.stdin.readline().strip())
    graph = {}
    for i in range(n):
        graph[i] = {}
    for i in range(m):
        a, b, t = map(int, sys.stdin.readline().strip().split())
        graph[a][b] = t
        graph[b][a] = t
    x = [0] * (n + 1)
    min_cost = 0
    x[0] = 0 # 出发节点：路径x的第一个节点（随便哪个）
    tsp(1)   # 开始处理解x中的第2个节点
    if min_cost == 0:
        print(-1)
    else:
        print(min_cost)