虽然只拿了20分，但是因为思路比较重要，还是决定记录一下
这个题n的数据规模是 [1, 20]，所以思路就是 图 + 状态压缩
首先读取输入，得出这个图的邻接矩阵
from math import infnum, limit = map(int, input().split())loc = [list(map(int, input().split())) for idx in range(num)]# 记录每个顶点的坐标adj = [[inf for _ in range(num)] for __ in range(num)]# 初始化邻接矩阵for begin in range(num): x_b, y_b = loc[begin] for end in range(begin + 1, num): x_e, y_e = loc[end] value = ((x_b - x_e) ** 2 + (y_b - y_e) ** 2) ** 0.5 # 计算距离 if value <= limit: adj[begin][end] = adj[end][begin] = value # 如果距离允许则直接填入邻接矩阵
用二进制数来表示经过的地点。如0000表示停留在起点 (第1个地点) 未经过任何地点，0010表示从起点出发经过第2个地点，1111表示从起点出发经过第2、3、4个地点并返回起点。现在依据“经过几个地点”对二进制状态进行分层
bin函数可以将整数转化为二进制字符串，如：5 -> "0b101"。定义函数count_1得出经过地点的数目n，然后利用位运算筛除所有包含第1个地点的状态。假设总共有4个地点，因为第1个地点是要最后到达的，所以最终状态应该是1111 (15)，即 (1 << 4) - 1，把这个状态分在最后一层
def count_1(num): return bin(num).count("1")dp = [{} for _ in range(num + 1)]# 索引为n的字典记录已经过起点和n个地点的状态for choose in range(1 << num): if not choose & 1: # 筛选掉所有包含起点的状态 dp[count_1(choose)][choose] = infdp[-1][(1 << num) - 1] = inf# 在最后一层添加包含起点的状态dp[0][0] = 0# 初始化起始状态
在创建邻接矩阵的时候已经保证了飞机单次飞行的距离不会超限，但这样使在做状态转移时需要考虑某地点被多次经过、状态转移过于繁琐。所以用一下Floyd算法处理一下邻接矩阵，求出多源最短路
def Floyd(): for mid in range(num): for begin in range(num): for end in range(begin + 1, num): state = min([adj[begin][end], adj[begin][mid] + adj[mid][end]]) adj[begin][end] = adj[end][begin] = stateFloyd()# 求出多源最短路
我记得我看的教程是用了三维矩阵，但是我觉得没必要，直接在邻接矩阵上面动手就可以。笔者不才，也没法说个所以然
用一维列表stay记录一下每个状态对应的停留点，就可以逐层做状态转移了
stay = [num for _ in range(1 << num)]# 记录每个状态对应的最终停留点stay[0] = 0for count in range(1, num + 1): for last_choose in dp[count - 1]: # 遍历上一个状态 last_dist = dp[count - 1][last_choose] # 上一个状态对应的距离 begin = stay[last_choose] # 上一个状态的停留点记为begin if last_dist < inf: for cur_choose in dp[count]: # 遍历当前状态 if last_choose | cur_choose == cur_choose: # 状态转移合法 cur_dist = dp[count][cur_choose] new = len(bin(cur_choose - last_choose)[2:]) - 1 # 当前状态停留点记为new state = last_dist + adj[begin][new] # 当前状态对应的距离 if state < cur_dist: # 比较取最优 stay[cur_choose] = new dp[count][cur_choose] = state
last_choose (二进制状态) 取自 dp[count-1]，cur_choose 取自 dp[count]，所以已经过地点的数目必满足：cur_choose - last_choose == 1。假设last_choose是0010，cur_choose是0101，利用 last_choose | cur_choose == cur_choose 这个条件可以筛除掉这种不合法的状态转移
假设last_choose是0010，cur_choose是0110，cur_choose - last_choose = 0100，用len(bin(cur_choose - last_choose[2:])) - 1 可以求出新经过的地点索引
最后输出最后一层唯一一个状态的值
result = dp[-1].popitem()[1]print(f"{round(result, 2):.2f}")
思路看着没问题哇，如果有好心人给个测评数据校对就好了 —— 也请各路大佬指正