题目描述

给定一个分层的无向图，包含 $N$ 个节点和 $M$ 条额外的带权边。每个节点 $i$ 属于一个特定的层 $l_i$。

图中存在两种移动方式：

1. 阶梯移动: 从任意一层的任意节点，可以移动到其相邻层（上一层或下一层）的任意节点。每次阶梯移动的成本固定为 $C$。
2. 额外边移动: 对于给定的 $M$ 条额外边 $(u, v)$，可以在节点 $u$ 和 $v$ 之间双向移动，成本为该边对应的权值 $w$。

目标是计算从节点 $1$ 移动到节点 $N$ 所需的最低总成本。如果无法到达节点 $N$，则输出 $-1$。

样例

输入样例：
2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3
3 3 3
1 3 2
1 2 2
2 3 2
1 3 4

输出样例：
Case #1: 2
Case #2: 3

算法 (Dijkstra + 虚拟节点优化)

思路分析

这是一个典型的单源最短路径问题，目标是从节点 1 找到到达节点 N 的最小成本路径。图中存在两种类型的边：已有的额外边和隐含的阶梯移动边。

1. 额外边: 这些边可以直接添加到图模型中。由于是双向移动，对于边 $(u, v, w)$，我们需要在图中添加两条有向边：$u \to v$ (成本 $w$) 和 $v \to u$ (成本 $w$)。

2. 阶梯移动: 这是问题的关键。”从任意一层的任意一个节点移动至其相邻层（上一层或下一层）的任意一个节点，花费固定成本 $C$”。如果直接将所有可能的阶梯移动都表示为图中的边，会导致边的数量非常庞大。例如，如果层 $k$ 有 $N_k$ 个节点，层 $k+1$ 有 $N_{k+1}$ 个节点，那么仅仅在这两层之间，就需要添加 $N_k \times N_{k+1}$ 条从层 $k$ 到层 $k+1$ 的边，以及 $N_{k+1} \times N_k$ 条从层 $k+1$ 到层 $k$ 的边，这在 $N$ 很大时是不可接受的。

虚拟节点优化

为了高效地处理阶梯移动，我们引入虚拟节点。

• 为每个层创建代表节点: 假设图中最多有 $L$ 层 (即 $L = \max(l_i)$)。我们为每一层 $k$ ($1 \le k \le L$) 创建两种虚拟节点：

  • 出层节点 (Out-Node): out_k，代表从层 $k$ “出发” 进行阶梯移动的起点。
  • 入层节点 (In-Node): in_k，代表通过阶梯移动 “到达” 层 $k$ 的终点。

• 节点编号: 为了区分原始节点和虚拟节点，我们可以给虚拟节点分配新的编号。假设原始节点编号为 $1$ 到 $N$。

  • 出层节点 out_k 可以编号为 $N + k$。
  • 入层节点 in_k 可以编号为 $N + L + k$。
    这样，图的总节点数变为 $N + 2L$。

• 构建新的边:

  1. 原始节点 <-> 虚拟节点:
     • 对于层 $k$ 中的每个原始节点 $i$ ($l_i = k$)：
       • 添加一条从 $i$ 到 out_k 的边，成本为 0 ($i \to out_k$, cost 0)。这表示节点 $i$ 可以无成本地到达其所在层的“出发点”。
       • 添加一条从 in_k 到 $i$ 的边，成本为 0 ($in_k \to i$, cost 0)。这表示从其他层通过阶梯到达层 $k$ 的“到达点”后，可以无成本地进入层内的节点 $i$。
  2. 虚拟节点之间的阶梯移动:
     • 对于每一层 $k$ ($1 < k \le L$)，添加一条从 out_k 到 in_{k-1} 的边，成本为 $C$ ($out_k \to in_{k-1}$, cost $C$)。这代表从层 $k$ 向下移动到层 $k-1$。
     • 对于每一层 $k$ ($1 \le k < L$)，添加一条从 out_k 到 in_{k+1} 的边，成本为 $C$ ($out_k \to in_{k+1}$, cost $C$)。这代表从层 $k$ 向上移动到层 $k+1$。

• 为什么这样可行?
  考虑从层 $k$ 的节点 $u$ 通过阶梯移动到层 $k+1$ 的节点 $v$ 的过程。在新的图模型中，这条路径对应于：
  $u \xrightarrow{\text{cost } 0} out_k \xrightarrow{\text{cost } C} in_{k+1} \xrightarrow{\text{cost } 0} v$
  这条路径的总成本是 $0 + C + 0 = C$，正好等于一次阶梯移动的成本。通过引入虚拟节点，我们将原来可能存在的 $O(N^2)$ 级别的阶梯移动边，转化为了 $O(N)$ (原始节点与虚拟节点连接) + $O(L)$ (虚拟节点之间连接) 级别的边，大大减少了图的边数。

最短路径计算

在构建好包含虚拟节点的图之后，问题就转化为了一个标准的单源最短路径问题。因为所有边的成本都是非负的，我们可以使用 Dijkstra 算法来找到从源点（节点 1）到目标点（节点 N）的最短路径。

1. 初始化距离数组 d，d[1] = 0，其他节点的距离设为无穷大。
2. 使用优先队列（最小堆）来维护待处理的节点，初始时将 (0, 1) 加入队列。
3. 循环执行 Dijkstra 算法：取出队首距离最小的节点 u，遍历其所有邻居 v，如果通过 u 到达 v 的路径 d[u] + cost(u, v) 比当前的 d[v] 更短，则更新 d[v] 并将 (d[v], v) 加入优先队列。
4. 算法结束后，d[N] 就是节点 1 到节点 N 的最短距离。如果 d[N] 仍然是无穷大，则表示无法到达，输出 -1。

时间复杂度

• 图的构建:
  • 节点数 $V = N + 2L$。由于 $L \le N$，所以 $V = O(N)$。
  • 边数 $E$：
    • $M$ 条额外边 $\implies 2M$ 条有向边。
    • $N$ 个原始节点连接到出层节点 $\implies N$ 条边。
    • 入层节点连接到 $N$ 个原始节点 $\implies N$ 条边。
    • 虚拟节点之间的阶梯移动边 $\implies 2(L-1)$ 条边。
    • 总边数 $E = O(M + N + L) = O(M + N)$。
• Dijkstra 算法: 使用优先队列的实现，时间复杂度为 $O(E \log V)$ 或 $O(E + V \log V)$，具体取决于优先队列的实现。在本题中，为 $O((N+M) \log N)$。

总的时间复杂度为 $O((N+M) \log N)$。

C++ 代码解释

#include <bits/stdc++.h> // 包含常用的 STL 头文件

using namespace std;
using i64 = long long; // 使用 long long 存储距离，防止溢出

constexpr i64 inf = 2e18; // 定义一个足够大的数表示无穷大

void solve() {
    int n, m; // n: 节点数, m: 额外边数
    i64 c;    // c: 阶梯移动成本 (注意：这里用了 i64，虽然题目范围是 10^3，但路径总成本可能很大)
    cin >> n >> m >> c;

    vector<int> l(n + 1); // 存储每个节点所在的层数 (下标从 1 开始)
    for (int i = 1; i <= n; i ++ ) {
        cin >> l[i];
    }

    // 找到最大的层数 L
    int L = 0; // 如果 n=0，L 保持 0
    if (n > 0) {
        L = *max_element(l.begin() + 1, l.end());
    }

    // 计算总节点数，包括原始节点和虚拟节点
    // 节点 1~n: 原始节点
    // 节点 n+1 ~ n+L: 出层节点 (out_k 对应 n+k)
    // 节点 n+L+1 ~ n+2L: 入层节点 (in_k 对应 n+L+k)
    int total = n + 2 * L;

    // 构建图的邻接表，存储 pair<邻接节点, 边权>
    vector<vector<pair<int, i64>>> g(total + 1);

    // 1. 添加 M 条额外边 (双向)
    for (int i = 0; i < m; i ++ ) {
        int u, v;
        i64 w; // 边权也用 i64
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    // 2. 添加原始节点与虚拟节点的连接边 (成本为 0)
    for (int i = 1; i <= n; i ++ ) {
        int layer = l[i];       // 节点 i 所在的层
        int out_k = n + layer;  // 对应层的出层节点编号
        int in_k = n + L + layer; // 对应层的入层节点编号
        // 原始节点 i -> 出层节点 out_k (成本 0)
        g[i].push_back({out_k, 0});
        // 入层节点 in_k -> 原始节点 i (成本 0)
        g[in_k].push_back({i, 0});
    }

    // 3. 添加虚拟节点之间的阶梯移动边 (成本为 c)
    for (int k = 1; k <= L; k ++ ) {
        int out_k = n + k;        // 当前层的出层节点
        // int in_k = n + L + k; // 当前层的入层节点 (在此循环中未使用)

        // 向下移动: out_k -> in_{k-1} (如果 k > 1)
        if (k > 1) {
            int in_prev = n + L + (k - 1); // 下一层(k-1)的入层节点
            g[out_k].push_back({in_prev, c});
        }
        // 向上移动: out_k -> in_{k+1} (如果 k < L)
        if (k < L) {
            int in_next = n + L + (k + 1); // 上一层(k+1)的入层节点
            g[out_k].push_back({in_next, c});
        }
    }

    // 4. 执行 Dijkstra 算法
    vector<i64> d(total + 1, inf); // 距离数组，初始化为无穷大
    // 优先队列，存储 pair<距离, 节点>，按距离从小到大排序
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<>> pq;

    // 起点是节点 1
    if (n >= 1) { // 处理 n=0 的边界情况
        d[1] = 0;
        pq.push({0, 1});
    }

    while (!pq.empty()) {
        // 取出当前距离最小的节点
        auto [dist, u] = pq.top();
        pq.pop();

        // 如果当前取出的距离比已经记录的距离大，说明是旧信息，跳过
        if (dist > d[u]) continue;

        // 遍历节点 u 的所有邻居 v
        for (auto [v, w] : g[u]) {
            i64 cur = dist + w; // 计算通过 u 到达 v 的新距离
            // 如果新距离更短
            if (cur < d[v]) {
                d[v] = cur; // 更新最短距离
                pq.push({cur, v}); // 将更新后的节点加入优先队列
            }
        }
    }

    // 5. 输出结果
    // 检查节点 N 是否可达 (N 必须存在且大于等于 1)
    i64 res = -1;
    if (n >= 1) { // 只有 n>=1 时目标节点 n 才有效
       res = (d[n] < inf) ? d[n] : -1; // 如果 d[n] 不是无穷大，则为最短距离，否则为 -1
    } else if (n == 0) { // 如果 n=0，没有节点，无法从 1 到 N(0)，视为不可达
        res = -1;
    }
    // 特殊情况：如果 n=1，起点即终点，距离是 0，代码能正确处理 (d[1]=0)

    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false); // 加速 cin/cout
    cin.tie(nullptr);

    int t; // 测试数据组数
    cin >> t;

    for (int i = 1; i <= t; i ++ ) {
        cout << "Case #" << i << ": "; // 按格式输出 Case 编号
        solve(); // 调用解决函数处理每组数据
    }

    return 0;
}