给定n个城市(从0到n-1),3元组[A, B, C]表示城市A和城市B之间存在道路,且成本为C。计算从0号城市出发,旅行完每个城市一遍,最后回到0号城市的最小成本与路径。如果不存在最优方案,输出-1 这道题的完整代码
时间: 2023-11-27 13:51:54 浏览: 34
这是一个经典的旅行商问题(TSP),可以使用动态规划和状态压缩来解决。以下是代码实现:
```python
import sys
def tsp(n, edges):
# 构建邻接矩阵
graph = [[float('inf')] * n for _ in range(n)]
for a, b, c in edges:
graph[a][b] = c
# dp数组,dp[S][i]表示经过集合S中的所有节点,最后停留在i节点的最短路径
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0
for S in range(1, 1 << n):
if S & 1 == 0: # 保证起点为0
continue
for i in range(n):
if S & (1 << i) == 0: # i不在集合S中
continue
for j in range(n):
if i == j or graph[j][i] == float('inf') or S & (1 << j) == 0:
continue
dp[S][i] = min(dp[S][i], dp[S ^ (1 << i)][j] + graph[j][i])
res = min(dp[(1 << n) - 1][i] + graph[i][0] for i in range(n))
return res if res != float('inf') else -1
if __name__ == '__main__':
n = int(input().strip())
edges = []
for _ in range(n):
a, b, c = map(int, input().split())
edges.append((a, b, c))
res = tsp(n, edges)
print(res)
```
其中,`n`表示城市数量,`edges`为道路信息列表,每个元素为一个三元组`(A, B, C)`,表示A城市和B城市之间有一条成本为C的道路。
算法基于状态压缩的动态规划,使用`dp[S][i]`表示经过集合`S`中的所有节点,最后停留在`i`节点的最短路径。其中,`S`是一个二进制数,表示包含哪些节点,例如`S=1011`表示包含节点0、1、3。初始状态为`dp[1][0]=0`,即只包含节点0的集合。
状态转移方程为:`dp[S][i] = min(dp[S][i], dp[S ^ (1 << i)][j] + graph[j][i])`,其中`S ^ (1 << i)`表示将集合S中的第i位取反(如果原来是0就变成1,如果是1就变成0),表示从S中删除i节点;`j`表示从哪个节点到达`i`节点,遍历所有可能的`j`,取最小值即可。
最终结果为`min(dp[(1 << n) - 1][i] + graph[i][0] for i in range(n))`,即遍历所有节点后回到起点的最小成本。如果结果为`float('inf')`,表示无法遍历所有节点,输出-1即可。