题目简述

给定一个网格，每个单元格代表不同的通信方式及代价。起点为左上角 (0, 0)，终点为右下角 (n-1, m-1)，你需要计算从起点到终点的最小代价路径。路径只能在上下左右四个方向移动，且不能穿越值为-1的单元格。如果无法到达终点，返回-1。

通信方式的代价分别为：

• 3: 有线通信
• 20: 短波通信
• 13: 超短波通信
• -1: 无连接（不可通过）

解题思路

本题要求的是寻找一个从起点到终点的最短路径代价，可以用Dijkstra算法来解决。Dijkstra算法是解决带权图中从起点到各个节点最短路径问题的经典算法，特别适用于边权非负的情况。

• 图的表示：每个网格单元可以看作图中的一个节点，节点间的边表示上下左右相邻单元之间的路径，边的权值为该节点的值（3、20、13）。
• 优先队列：我们使用最小堆（优先队列）来进行Dijkstra算法的实现，从起点开始，不断扩展到邻居节点，直到找到终点或者遍历完所有可达的节点。

主要步骤：

1. 边界检查：检查起点和终点是否可达。
2. Dijkstra算法：用优先队列维护当前最小路径代价，通过四个方向遍历相邻的节点，更新最小代价并加入队列。
3. 返回结果：当找到终点时返回当前的代价，如果遍历结束仍未到达终点，返回-1。

复杂度分析

• 时间复杂度：Dijkstra算法的时间复杂度为 O((n * m) log(n * m))，其中n * m是网格的大小，log(n * m)是优先队列的操作复杂度。
• 空间复杂度：O(n * m)，需要保存最小代价和堆。

Python 代码实现

import heapq

# 定义四个方向，分别为上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def find_min_cost_path(n, m, grid):
    # 边界检查，确保起点和终点可达
    if grid[0][0] == -1 or grid[n-1][m-1] == -1:
        return -1
    
    # 创建一个最小堆用于Dijkstra算法
    heap = []
    heapq.heappush(heap, (grid[0][0], 0, 0))  # (当前路径的代价, x, y)
    
    # 创建一个二维数组用于存储最小代价
    min_cost = [[float('inf')] * m for _ in range(n)]
    min_cost[0][0] = grid[0][0]
    
    while heap:
        current_cost, x, y = heapq.heappop(heap)
        
        # 如果当前节点是终点，则返回代价
        if x == n - 1 and y == m - 1:
            continue
        
        # 遍历上下左右四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != -1:
                new_cost = current_cost + grid[nx][ny]
                # 如果找到更小的代价，更新并加入堆
                if new_cost < min_cost[nx][ny]:
                    min_cost[nx][ny] = new_cost
                    heapq.heappush(heap, (new_cost, nx, ny))
    
    # 如果无法到达终点，返回 -1
    return min_cost[n-1][m-1] if min_cost[n-1][m-1] != float('inf') else -1

# 输入处理
n, m = map(int, input().split())  # 输入矩阵的行数和列数
grid_str = input().strip().replace("{", "[").replace("}", "]")  # 输入矩阵的字符串表示

grid = eval(grid_str)  # 可以用 eval 来处理输入的格式

# 计算最小代价路径
result = find_min_cost_path(n, m, grid)
print(result)

题目内容

往往由于地理位置、距离等各种因素影响需要使用有线、无线等手段进行混合组网，然而每种通信方式的代价都不尽相同，比如有线组网时延就比无线组网低很多，由于数据传输过程中需要经过多个节点，而且每个节点间连线方式不同，所以合理路由算法就显得格外的重要。现假设我们有3 种通信方式及代价:有线【$Wire$&$3$】、短波【$Short wave$&$20$】、超短波【$Ultra short wave$&$13$】。

现给出一个$m*n$组网图(矩阵表示，数字分别是$3/20/13$，其中$-1$说明没有链接)，求出从$S$起点到$E$终点的最优路径的代价和，其中$-1$不能作为路径上的节点且路径仅支持上下左右四个方向。

输入描述

第一行:输入$n[1,10^6]$; $m [1,10^6]$，描述矩阵的大小

第二行:输入整型矩阵，，每一个元素使用代价$【3、20、13、-1】$做为填充值;$3$代表有线，$20$代表短波，$13$代表超短波，$-1$代表未链接。

说明: 起点$S$为$[0,0]$

终点$E$为$【n-1,m-1】$

输出描述

输出组网单包最小代价路径，如果无法到达，返回$-1$。

样例1

输入

3 3
{{3,20,13},{-1,-1,3},{-1,-1,3}}

输出

42

说明

3 20 13
-1 -1 3
-1 -1 3

唯一的路线是$3->20->13->3->3$

样例2

输入

3 3
{{3,20,13},{3,-1,3},{3,3,3}}

输出

15

说明

3 20 13
3 -1 3
3 3 3

最小代价路线$3->3->3->3->3$;还有一条路线的是$3->20->13->3->3$大于最小路径