Python面试题：如何基于两个列表计算两座岛屿间的最低票价

题目给定条件 #

• 全局列表定义：

islands = [isl_1, isl_2, isl_3, isl_4]
tickets = [0, 100, 200, 300, 2, 0, 25, 170, 10, 20, 0, 300, 540, 80, 60, 0]

• tickets规则：每4个元素为一组，依次对应isl_1到isl_4作为出发地，到所有4个岛屿的票价，值为0代表出发与目的地为同一岛屿。
• 要求实现函数：def cheapest_ticket(from_isl, to_isl)，返回两个岛屿之间的最低票价。

解题思路 #

本题本质是带权有向图的最短路径问题，一共只有4个节点（岛屿），计算量极小，采用Floyd-Warshall算法预计算所有节点对的最短路径，后续查询可以直接返回结果，效率极高。

完整实现代码 #

# 预先构建岛屿到下标的映射、邻接矩阵、最短路径矩阵
island_to_idx = {isl: idx for idx, isl in enumerate(islands)}
node_count = len(islands)
# 初始化邻接矩阵
adj_matrix = [tickets[i*4 : (i+1)*4] for i in range(node_count)]
# 初始化最短路径矩阵
dist = [row[:] for row in adj_matrix]

# Floyd算法计算所有节点对最短路径
for k in range(node_count):
    for i in range(node_count):
        for j in range(node_count):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

def cheapest_ticket(from_isl, to_isl):
    # 校验输入合法性
    if from_isl not in island_to_idx or to_isl not in island_to_idx:
        raise ValueError("输入的岛屿不存在")
    from_idx = island_to_idx[from_isl]
    to_idx = island_to_idx[to_isl]
    return dist[from_idx][to_idx]

测试示例 #

比如查询isl_1到isl_4的最低票价：

cheapest_ticket(isl_1, isl_4)

返回结果为270，路径为isl_1 -> isl_2 -> isl_4，总票价100+170=270，比直达的300更便宜。

内容的提问来源于stack exchange，提问作者Mike L