A37463. 小蓝从公司出发，要去拜访N（3≤N≤15）个客户，已知公司到每个客户的路程时间，及N个客户之间的路程时间。请计算出小蓝拜访完所有客户并返回到公司，最少需要多少时间。（道路双向通行，可重复走）例如：N = 3，有3个客户需要拜访，公司到1号、2号、3号客户的路程时间依次为9，7，5，客户1到客户2和客户3的路程时间依次是4，6，客户2到客户3的路程时间是3。从公司出发拜访完3名客户并返回…
填空题
困难
知识点
题目描述
题目描述：
小蓝从公司出发，要去拜访N（3≤N≤15）个客户，已知公司到每个客户的路程时间，及N个客户之间的路程时间。请计算出小蓝拜访完所有客户并返回到公司，最少需要多少时间。（道路双向通行，可重复走）
例如：N = 3，有3个客户需要拜访，公司到1号、2号、3号客户的路程时间依次为9，7，5，客户1到客户2和客户3的路程时间依次是4，6，客户2到客户3的路程时间是3。
从公司出发拜访完3名客户并返回公司最少需要的路程时间为21，行走路线为：公司 --> 3号 --> 2号 --> 1号--> 公司（21=5+3+4+9）。
输入描述
1）第一行输入一个正整数N（3≤N≤15），表示要拜访的客户数量
2）第二行输入N个正整数（1≤正整数≤1000），依次表示公司到1号~N号客户的路程时间，正整数之间以一个空格隔开
3)第三行输入N-1个正整数（1≤正整数≤1000），依次表示1号客户到2号~N号客户的路程时间，正整数之间以一个空格隔开
4)第四行输入N-2个正整数（1≤正整数≤1000），依次表示2号客户到3号~N号客户的路程时间，正整数之间以一个空格隔开
......
第N+1行输入一个正整数（1≤正整数≤1000），表示N-1号客户到N号客户的路程时间
输出描述
输出一个整数，表示小蓝拜访完N名客户并返回公司最少需要的路程时间
样例输入
3
9 7 5
4 6
3
样例输出
21
参考答案
from itertools import permutations
n=int(input())
ls=[]
for i in range(n):
ls.append(list(map(int,input().split())))
while len(ls[i])<n:
ls[i].append(0)
ans=16000
sum=0
arr = [i for i in range(1,n+1)]
for perm in permutations(arr):
sum=ls[0][perm[0]-1]+ls[0][perm[-1]-1]
for j in range(1,n):
if perm[j-1]<perm[j]:
sum+=ls[perm[j-1]-1][perm[j]-1]
else:
sum += ls[perm[j]-1][perm[j-1]-1]
ans=min(ans,sum)
print(ans)
上一题
下一题