回溯法 代码 给定n个城市（从0到n-1），3元组[A, B, C]表示城市A和城市B之间存在道路，且成本为C。计算从0号城市出发，旅行完每个城市一遍，最后回到0号城市的最小成本与路径。如果不存在最优方案，输出-1

下面是回溯法的代码实现：

def tsp_backtrack(graph):
    n = len(graph)
    visited = [False] * n
    visited[0] = True
    path = [0]
    min_cost = float('inf')
    
    def backtrack(curr, cost):
        nonlocal min_cost
        
        if len(path) == n:
            if graph[curr][0] != 0:
                cost += graph[curr][0]
                min_cost = min(min_cost, cost)
            return
        
        for i in range(n):
            if not visited[i] and graph[curr][i] != -1:
                visited[i] = True
                path.append(i)
                backtrack(i, cost + graph[curr][i])
                path.pop()
                visited[i] = False
    
    backtrack(0, 0)
    return min_cost if min_cost != float('inf') else -1

其中，graph是一个二维数组，表示城市之间的道路和成本，-1表示两个城市之间没有道路。例如，graph[i][j]表示城市i到城市j的道路成本。

该算法的时间复杂度为O(n!)，因为它需要枚举所有可能的路径。在实际应用中，当n较大时，该算法的计算成本会非常高，因此不适合处理大规模问题。