依图算法笔试第二题，大胃王那一题，回溯超时求指导
用回溯的方法为什么会超时呢？
写个回溯容易嘛
import sys
n,m,start,end = map(int,sys.stdin.readline().strip().split())
start -= 1
end -= 1
cakes = map(int,sys.stdin.readline().strip().split())
matrix = [[0] * n for _ in range(n)]
total = [sys.maxsize - 1]
rs = {}
for _ in range(m):
nums = map(int,sys.stdin.readline().strip().split())
matrix[nums[0]-1][nums[1]-1] = nums[2]
#def conflict(i,cur_path):
# if i in cur_path or matrix[cur_path[-1]][i] == 0:
# return True
# return False
def back(cur_path,cur_time,cur_num):
# print(cur_path,cur_time,cur_num,total,rs)
if cur_path[-1] == end:
if cur_time <= total[-1]:
total.append(cur_time)
if cur_time not in rs:
rs[cur_time] = cur_num
else:
rs[cur_time] = max(cur_num,rs[cur_time])
# if cur_num > rs[-1]:
# rs.append(cur_num)
return
for i in range(cur_path[-1],n):
if i in cur_path or matrix[cur_path[-1]][i] == 0:
continue
else:
back(cur_path+[i],cur_time+matrix[cur_path[-1]][i],cur_num+cakes[i])
back([start],0,cakes[start])
#tmp = " ".join(map(str,[total[-1],rs[total[-1]]]))
print total[-1],
print rs[total[-1]] 有大佬能知道一下嘛
查看10道真题和解析