题目大意

有 $n$ 只宝可梦，每只宝可梦有 $m$ 项属性 $a_{i,j}$，雇佣第 $i$ 只宝可梦的费用为 $c_i$。
初始时第 $1$ 只宝可梦站在竞技场中。你可以进行两种操作任意次：

1. 选择 $(i,j,k)$，将 $a_{i,j}$ 增加 $k$，花费 $k$；
2. 选择 $(i,j)$，雇佣第 $i$ 只宝可梦，基于第 $j$ 项属性与当前宝可梦决斗。若 $a_{i,j} \ge$ 当前宝可梦的第 $j$ 项属性，则第 $i$ 只获胜并留在场上，花费 $c_i$。

求让第 $n$ 只宝可梦最终获胜的最小总花费。

问题转化

一次决斗可以看作从当前宝可梦 $x$ 转移到另一只宝可梦 $z$，要求存在某个属性 $j$ 使得 $a_{z,j} \ge a_{x,j}$。
若不满足，可以先花费 $(a_{x,j}-a_{z,j})$ 提升 $a_{z,j}$，再花费 $c_z$ 雇佣 $z$ 进行决斗。
因此从 $x$ 到 $z$ 在属性 $j$ 上的转移代价为 $\max(0,\,a_{x,j}-a_{z,j}) + c_z$。

初始时第 $1$ 只宝可梦已在场，不需要支付 $c_1$。我们需要找到一条从 $1$ 到 $n$ 的路径，使得总代价最小。

图论建模

直接建 $n$ 个点的图，边权依赖于属性，且 $n$ 可达 $4\times 10^5$，$n\cdot m\le 4\times10^5$。
由于 $m$ 较小，可以利用属性维度将状态拆分为 $(i,j)$：表示“当前在场的宝可梦是 $i$，且最近一次决斗使用的属性是 $j$”。
对于每个状态 $(i,j)$，有两种扩展方式：

• 支付宝可梦 $i$ 的雇佣费：若 $i$ 尚未被雇佣（即第一次成为当前宝可梦），则必须支付 $c_i$，之后 $i$ 变为“已激活”状态，并且可以利用 所有属性 去挑战其他宝可梦。对应代码中的 if (!vis[x]) 分支。
• 通过属性 $j$ 挑战其他宝可梦：仅当 $i$ 已激活（已支付 $c_i$）时，可以沿着属性 $j$ 的数值顺序，向相邻排名的宝可梦转移。
  • 向 属性值更大 的宝可梦 $z$ 转移（排名 $+1$）：因为 $a_{z,j}\ge a_{i,j}$，无需提升，只需未来支付 $c_z$，所以转移代价为 $0$（代码中的向上转移）。
  • 向 属性值更小 的宝可梦 $z$ 转移（排名 $-1$）：需要将 $a_{z,j}$ 提升到 $a_{i,j}$，代价为 $a_{i,j}-a_{z,j}$，加上未来支付 $c_z$，所以转移代价为 $a_{i,j}-a_{z,j}$（代码中的向下转移）。

状态与算法

定义 dist[i][j] 表示到达状态 $(i,j)$ 的最小 已花费（此时 $i$ 尚未支付 $c_i$，即 vis[i]=0）。
初始时宝可梦 $1$ 已在场且已激活（无需支付），所以对所有 $j$，dist[1][j]=0，vis[1]=1，并加入优先队列。

运行 Dijkstra：

• 取出当前状态 $(x,j)$ 及其花费 $w$。
• 如果 vis[x]==0（未激活），则激活它：支付 $c_x$，更新所有 dist[x][j] = w + c_x，标记 vis[x]=1，并将 $(w+c_x, x, j)$ 入队（每个属性 $j$ 都入队）。
• 否则 vis[x]==1（已激活）：
  • 如果 $x=n$，用 $w$ 更新答案。
  • 在属性 $j$ 的排序数组中，找到 $x$ 的相邻排名宝可梦：
    • 向上（属性更大）：设 $z$ 为排名 $+1$ 的宝可梦，若 w < dist[z][j]，则更新 dist[z][j] = w 并推入队列。
    • 向下（属性更小）：设 $z$ 为排名 $-1$ 的宝可梦，代价 cost = w + a[x][j] - a[z][j]，若 cost < dist[z][j]，则更新并推入队列。

最终答案为 $\min\{w \mid (n,j)\text{ 被激活时的 }w\}$。

正确性与复杂度

• 每条从 $1$ 到 $n$ 的合法操作序列都可以映射为图上的一条路径，且边权非负，Dijkstra 保证求出最短路径。
• 每个状态 $(i,j)$ 最多被扩展两次（向上/向下），每个节点 $i$ 激活后需遍历 $m$ 个属性。总状态数为 $n\cdot m$，而 $\sum n\cdot m \le 4\times10^5$，所以总复杂度 $O(\sum n\cdot m \log(n\cdot m))$，可以通过。

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> c(n + 1);
        for (int i = 1; i <= n; i++) cin >> c[i];

        vector<vector<int>> a(n + 1, vector<int>(m + 1));
        vector<vector<pair<int, int>>> b(m + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
                b[j].push_back({a[i][j], i});
            }
        }

        vector<vector<int>> rank(n + 1, vector<int>(m + 1));
        vector<vector<int>> dec(n + 1, vector<int>(m + 1));
        for (int j = 1; j <= m; j++) {
            sort(b[j].begin(), b[j].end());
            for (int i = 0; i < n; i++) {
                auto [x, id] = b[j][i];
                rank[id][j] = i + 1;
                dec[i + 1][j] = id;
            }
        }

        int ans = INFF;
        vector<int> vis(n + 1, 0);
        vector<vector<int>> dist(n + 1, vector<int>(m + 1, INFF));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

        // 宝可梦 1 初始在场，视为已支付（无需花费）
        vis[1] = 1;
        for (int j = 1; j <= m; j++) {
            dist[1][j] = 0;
            pq.push({0, 1, j});
        }

        while (!pq.empty()) {
            auto [w, x, t] = pq.top();
            pq.pop();
            if (dist[x][t] < w) continue;

            // 如果当前宝可梦尚未支付雇佣费，则支付并扩散到所有属性，然后跳过当前状态
            if (!vis[x]) {
                vis[x] = 1;
                for (int j = 1; j <= m; j++) {
                    int new_w = w + c[x];
                    if (new_w < dist[x][j]) {
                        dist[x][j] = new_w;
                        pq.push({new_w, x, j});
                    }
                }
                continue;
            }

            // 已支付状态：更新答案
            if (x == n) ans = min(ans, w);

            // 同属性内转移（向上）
            if (rank[x][t] < n) {
                int z = dec[rank[x][t] + 1][t];
                if (w < dist[z][t]) {
                    dist[z][t] = w;
                    pq.push({w, z, t});
                }
            }
            // 同属性内转移（向下）
            if (rank[x][t] > 1) {
                int z = dec[rank[x][t] - 1][t];
                int cost = w + a[x][t] - a[z][t];
                if (cost < dist[z][t]) {
                    dist[z][t] = cost;
                    pq.push({cost, z, t});
                }
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

代码实现要点

• 对每个属性 $j$ 分别排序，记录每个宝可梦在该属性上的排名，以及按排名顺序的宝可梦编号。
• 使用优先队列（小根堆）存储 (cost, pokemon_id, attribute_id)。
• vis 数组记录宝可梦是否已激活（是否已支付其 $c_i$）。
• 注意 dist 初始化为无穷大，$c_i$ 可能很大，使用 long long。