题意分析

题目要求贝西从网格的左上角$(1,1)$出发，以初始速度$V$移动至右下角$(R,C)$，每次移动只能向北、南、东、西四个方向，且移动时间受海拔变化影响。关键规则如下：

1. 速度变化：从海拔$A$移动到相邻位置海拔$B$时，速度$v$更新为： $v_{\text{new}} = v_{\text{old}} \times 2^{A-B}$

2. 时间计算：从位置$A$到相邻位置$B$的移动时间为出发时速度的倒数： $\text{time} = \frac{1}{v_{\text{old}}}$

目标：找到贝西从起点到终点的最短时间路径。

关键思路

虽然速度在移动过程中动态变化，但通过数学推导发现：任意位置$(i,j)$的速度仅取决于初始速度$V$和起点到该点的海拔差。具体地，从$(1,1)$到$(i,j)$的速度为： $v(i,j) = V \times 2^{E_{1,1} - E_{i,j}}$ 其中$E_{1,1}$和$E_{i,j}$分别为起点和目标点的海拔。因此，从$(i,j)$移动到相邻点$(i',j')$的时间可直接计算为： $ \text{time} = \frac{1}{V \times 2^{E_{1,1} - E_{i,j}}}. $

这一发现将问题转化为固定权值的最短路径问题，可用SPFA算法高效解决。

算法实现

以下是使用SPFA（Shortest Path Faster Algorithm）解决该问题的代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;

const double INF = 0x7fffffff; // double类型的无穷大
const int maxn = 110;
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1}; // 四个方向

struct NODE{
    int x, y;
};

bool vis[maxn][maxn]; // 标记节点是否在队列中
double e[maxn][maxn]; // 存储海拔数据
double t[maxn][maxn]; // 存储最短时间
double v; // 初始速度
int r, c; // 网格大小

void SPFA();

int main()
{
    while(scanf("%lf%d%d", &v, &r, &c) != EOF) {
        for(int i = 1; i <= r; i++) {
            for(int j = 1; j <= c; j++) {
                scanf("%lf", &e[i][j]);
            }
        }
        SPFA();
    }
    return 0;
}

void SPFA() {
    // 初始化最短时间数组为无穷大
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            t[i][j] = INF;
        }
    }
    t[1][1] = 0; // 起点时间为0

    memset(vis, 0, sizeof(vis));
    vis[1][1] = 1;
    queue<NODE> q;
    q.push((NODE){1,1});

    while(!q.empty()) {
        NODE tmp = q.front();
        q.pop();
        vis[tmp.x][tmp.y] = 0; // 清除标记

        // 计算从当前点出发的移动时间
        double w = 1.0 / (v * pow(2.0, e[1][1] - e[tmp.x][tmp.y]));

        // 遍历四个方向
        for(int k = 0; k < 4; k++) {
            int tx = tmp.x + dir[k][0];
            int ty = tmp.y + dir[k][1];

            // 边界检查
            if(tx < 1 || tx > r || ty < 1 || ty > c)
                continue;

            // 松弛操作
            if(t[tmp.x][tmp.y] < INF && t[tx][ty] > t[tmp.x][tmp.y] + w) {
                t[tx][ty] = t[tmp.x][tmp.y] + w;
                if(!vis[tx][ty]) {
                    vis[tx][ty] = 1;
                    q.push((NODE){tx,ty});
                }
            }
        }
    }

    // 输出结果，保留两位小数
    printf("%.2f\n", t[r][c]);
}

算法解析

1. 预处理与初始化：

   • 读取初始速度$V$和海拔矩阵$E$
   • 初始化最短时间数组$t$，起点$(1,1)$时间为0，其余为无穷大

2. SPFA算法核心：

   • 使用队列维护待处理的节点
   • 对于每个节点，计算其到相邻节点的移动时间（基于固定公式）
   • 若发现更短路径，则更新时间数组并将节点加入队列

3. 时间计算优化：

   • 每个节点$(i,j)$的速度仅由起点海拔和当前海拔决定
   • 移动时间计算不依赖路径，仅需常数时间$O(1)$

复杂度分析

• 时间复杂度：最坏情况下$O(R \times C \times 4)$，即每个节点入队约4次
• 空间复杂度：$O(R \times C)$，主要用于存储海拔和时间数组

该算法高效处理了题目中的动态速度变化问题，通过数学推导将其转化为静态权值最短路径问题，确保了计算效率和正确性。