小蓝从公司出发,要去拜访N (3<N<15)个客户,已知公司到每个客户的路程时间,及N个客户之间的路程时间。请计算出小蓝拜访完所有客户并返回到公司,最少需要多少时间。(道路双向通行,可重复走)例如:N=3,有3个客户需要拜访,公司到1号、2号、3号客户的路程时间依次为9,7,5,客户1到客户2和客户3的路程时间依次是4,6,客户2到客户3的路程时间是3。python代码实现
时间: 2024-02-13 15:06:56 浏览: 66
小蓝咖啡从0到1.pdf
以下是Python代码实现:
```python
import sys
N = int(sys.stdin.readline())
dist = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
line = sys.stdin.readline().strip().split()
for j in range(1, N+1):
dist[i][j] = int(line[j-1])
# 动态规划
dp = [[float('inf')] * (N+1) for _ in range(1<<N)]
dp[1][1] = 0 # 第一个客户是1号客户
for s in range(1<<N):
for i in range(1, N+1):
if s & (1<<(i-1)): # i号客户已经被拜访过了
for j in range(1, N+1):
if j != i and s & (1<<(j-1)): # j号客户也被拜访过了
dp[s][i] = min(dp[s][i], dp[s^(1<<(i-1))][j] + dist[j][i])
ans = float('inf')
for i in range(2, N+1):
ans = min(ans, dp[(1<<N)-1][i] + dist[i][1]) # 返回公司的时间要加上最后一个客户到公司的时间
print(ans)
```
注意,这个代码实现中,输入数据的格式是每行输入一个客户到所有其他客户的路程时间,需要根据这个格式修改输入部分的代码。
阅读全文