蓝桥杯 [第11届决赛] 补给 Python 20分

虽然只拿了20分，但是因为思路比较重要，还是决定记录一下

这个题n的数据规模是 [1, 20]，所以思路就是 图 + 状态压缩

首先读取输入，得出这个图的邻接矩阵

from math import inf

num, 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] = inf
dp[-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] = state
Floyd()
# 求出多源最短路

我记得我看的教程是用了三维矩阵，但是我觉得没必要，直接在邻接矩阵上面动手就可以。笔者不才，也没法说个所以然

用一维列表stay记录一下每个状态对应的停留点，就可以逐层做状态转移了

stay = [num for _ in range(1 << num)]
# 记录每个状态对应的最终停留点
stay[0] = 0
for 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}")

思路看着没问题哇，如果有好心人给个测评数据校对就好了 —— 也请各路大佬指正