### L2-036 网红点打卡问题的 Python 实现 以下是针对该问题的一个完整的 Python 解决方案。此问题是典型的最短路径问题，可以利用 Dijkstra 或 Floyd-Warshall 算法来解决。 #### 输入解析 输入数据描述了一个图结构，其中节点表示网红点和家的位置，边表示两点之间的连接及其费用。目标是从家出发到达指定顺序的网红点并返回家中，计算总最小花费[^2]。 #### 数据处理逻辑 为了简化问题，我们将整个过程分为以下几个部分： 1. 构建邻接矩阵或邻接表存储图的信息。 2. 使用算法求解从起点到其他各点的最短距离。 3. 计算按照给定顺序访问所有网红点所需的总成本，并加上回家的成本。 下面是基于上述思路的具体实现： ```python import heapq def dijkstra(graph, start): """Dijkstra's algorithm to find the shortest path from a single source.""" dist = {node: float('inf') for node in graph} dist[start] = 0 heap = [(0, start)] while heap: current_dist, u = heapq.heappop(heap) if current_dist > dist[u]: continue for v, weight in graph[u].items(): distance = current_dist + weight if distance < dist[v]: dist[v] = distance heapq.heappush(heap, (distance, v)) return dist def solve(n, m, home_to_points, point_connections, visit_order): # Step 1: Build adjacency list representation of the graph. graph = {} all_nodes = set(range(0, n + 1)) # Include 'home' as node 0 for i in all_nodes: graph[i] = {} for p1, p2, cost in point_connections + home_to_points: graph[p1][p2] = min(graph[p1].get(p2, float('inf')), cost) graph[p2][p1] = min(graph[p2].get(p1, float('inf')), cost) # Step 2: Use Dijkstra’s Algorithm to compute distances between nodes. distances_from_home = dijkstra(graph, 0) # Distances from home. total_cost = 0 prev_node = 0 # Start at home ('0'). try: for next_node in visit_order: total_cost += distances_from_home[next_node] prev_node = next_node distances_from_home = dijkstra(graph, prev_node) # Recompute after moving. # Add final trip back home. total_cost += distances_from_home[0] return total_cost except KeyError: return "Impossible" # Example Input Parsing and Execution if __name__ == "__main__": import sys input_data = sys.stdin.read().splitlines() line_index = iter(input_data) N, M = map(int, next(line_index).split()) home_to_points = [] point_connections = [] for _ in range(M): data = list(map(int, next(line_index).split())) if data[0] == 0 or data[1] == 0: home_to_points.append(data[:3]) else: point_connections.append(data[:3]) visit_order = list(map(int, next(line_index).split())) result = solve(N, M, home_to_points, point_connections, visit_order) print(result) ``` #### 关键说明 1. **Graph Construction**: 图通过 `graph` 字典构建，支持双向权重更新以确保最优路径被记录。 2. **Shortest Path Calculation**: 使用 Dijkstra 的优先队列版本高效查找单源最短路径。 3. **Total Cost Computation**: 遍历打卡序列逐步累加每次移动所需的时间/费用，并最终考虑回到原点的需求。 以上方法能够有效应对题目所设定的数据规模限制（最多 200 个节点）。如果存在无法完成的情况，则会输出 `"Impossible"` 表明无合法路线满足条件。 ---