题目背景与题意简述

Codeforces 1520G（题目链接）是一道结合广度优先搜索（BFS）与分层图思想的图论题，题目给定一个 ( n \times m ) 的网格，每个格子可能是：

• 空地（可通行，权值为 ( a_{i,j} )），
• 墙壁（不可通行，权值为 ( -1 )），
• 传送门（可传送到任意其他传送门，权值为 ( a_{i,j} )）。

玩家从起点 ( (1, 1) ) 出发，目标是到达终点 ( (n, m) )，移动规则如下：

• 每次可以向上下左右移动一格，花费为 ( w )（题目给定）。
• 若当前格子是传送门，可以免费传送到任意其他传送门。

求从起点到终点的最小总花费，若不可达则输出 -1。

解题思路

关键挑战：

• 直接BFS的局限性：普通BFS无法处理传送门的“全局跳跃”特性，因为每次跳跃可能涉及任意距离的转移，导致状态爆炸。
• 分层图优化：将问题转化为两层图：
  1. 物理层：通过普通移动（上下左右）连接相邻格子。
  2. 传送层：所有传送门之间通过虚拟边连接，权值为 ( a{u} + a{v} )（使用传送门需支付起点和终点的费用）。

具体步骤：

1. 预处理传送门：收集所有传送门的位置及其权值，记录全局最小权值的传送门（用于优化）。
2. 双源BFS：分别从起点和终点进行BFS，计算到每个传送门的最短物理距离。
3. 合并答案：
   • 直接物理移动的路径：( \text{dist_start}[n][m] )。
   • 通过传送门的路径：( \min(\text{dist_start}[u] + a_u) + \min(\text{dist_end}[v] + a_v) )。

代码实现要点（伪代码）

from collections import deque
def solve():
    n, m, w = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    # BFS函数：计算从(sx, sy)到各点的最短物理距离
    def bfs(sx, sy):
        dist = [[-1] * m for _ in range(n)]
        q = deque([(sx, sy)])
        dist[sx][sy] = 0
        while q:
            x, y = q.popleft()
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != -1 and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + w
                    q.append((nx, ny))
        return dist
    dist_start = bfs(0, 0)          # 从起点出发的物理距离
    dist_end = bfs(n-1, m-1)        # 从终点出发的物理距离
    # 收集所有传送门及其权值
    portals = []
    min_start_portal = float('inf')
    min_end_portal = float('inf')
    for i in range(n):
        for j in range(m):
            if grid[i][j] > 0:
                portals.append((i, j, grid[i][j]))
                if dist_start[i][j] != -1:
                    min_start_portal = min(min_start_portal, dist_start[i][j] + grid[i][j])
                if dist_end[i][j] != -1:
                    min_end_portal = min(min_end_portal, dist_end[i][j] + grid[i][j])
    # 计算答案
    ans = float('inf')
    if dist_start[n-1][m-1] != -1:
        ans = dist_start[n-1][m-1]
    if portals and min_start_portal + min_end_portal < ans:
        ans = min_start_portal + min_end_portal
    print(ans if ans != float('inf') else -1)
solve()

复杂度分析

• 时间：两次BFS为 ( O(nm) )，传送门预处理为 ( O(nm) )，总复杂度 ( O(nm) )。
• 空间：存储距离数组 ( O(nm) )。

本题通过分层图思想将复杂的最短路径问题拆解为物理移动和传送门跳跃两部分，避免了直接处理全局跳跃的高复杂度，类似的优化技巧也适用于其他需要处理“局部+全局”移动的图论问题。

关键收获：

• 灵活运用BFS的层次遍历特性。
• 通过预处理和分治降低问题规模。