题解 | #太阳系DISCO#

太阳系DISCO

https://www.nowcoder.com/practice/b9a31be4b1dd43c3b96d6bb3c178a5cd

题目链接

太阳系DISCO

题目描述

在一个由 $N$ 个行星构成的环形星系中，行星顺时针编号为 $1$ 到 $N$ （ $N$ 为偶数）。你从起点行星 $S$ 出发，目标是到达终点行星 $T$ 。你有以下三种移动方式，每种都消耗 1 单位时间：

顺时针移动 $X$ 颗行星。
逆时针移动 $Y$ 颗行星。
传送：顺时针移动 $N/2$ 颗行星（即跳到正对面）。此技能最多使用 $K$ 次。

请求出从 $S$ 到 $T$ 的最少时间。如果无法到达，输出 -1。

解题思路

这是一个在带有资源限制（传送次数）的图上求最短路径的问题。由于每次操作的成本都是 1，广度优先搜索 (BFS) 是最合适的算法。

核心思想：双层图模型

问题的关键在于如何处理传送技能和其次数限制。一个传送操作会将你送到环的对面，再传送一次就会回来。这启发我们构建一个“双层图”模型来描述状态：

第 0 层：代表通过偶数次传送到达的行星。
第 1 层：代表通过奇数次传送到达的行星。

整个状态空间可以看作是一个包含 $2 \times N$ 个节点的图。

状态：一个状态可以由 (行星编号, 所在层数) 唯一确定。
普通移动 (顺/逆时针)：不改变传送次数的奇偶性，因此是在同一层内部的转移。
传送移动：会改变传送次数的奇偶性，因此是在两层之间的转移。

带限制的 BFS

标准的 BFS 会找到最短的移动步数，但我们还需要确保该路径上的传送次数不超过 $K$ 。可能存在多条同样长度的最短路径，但它们的传送次数不同。我们需要的是那条传送次数最少的最短路径。

为此，我们可以在 BFS 中额外记录信息：

dist[N][2]: 存储到达行星 i 在第 j 层的最短时间。
min_teleports[N][2]: 存储到达行星 i 在第 j 层、且路径长度为最短时间时，所需要的最少传送次数。

算法流程

初始化：
- 创建 dist 和 min_teleports 两个二维数组，并初始化为无穷大。
- 将起点 (S, 0) 的信息初始化：dist[S][0] = 0，min_teleports[S][0] = 0。
- 创建一个队列，并将初始状态 (S, 0) 入队。
BFS 搜索：
- 从队列中取出状态 (u, layer)。
- 尝试三种移动方式（顺时针、逆时针、传送），计算出新状态 (v, new_layer)。
- 对于每个新状态，计算新的时间和传送次数。
  - new_dist = dist[u][layer] + 1
  - new_teleports = min_teleports[u][layer] + (1 if 传送 else 0)
- 更新 dist 和 min_teleports 数组：
  - 如果 new_dist < dist[v][new_layer]，说明找到了一条更短的路径。更新 dist 和 min_teleports，并将新状态入队。
  - 如果 new_dist == dist[v][new_layer]，说明找到了一条等长路径。此时，只在 new_teleports 更少的情况下更新 min_teleports。
获取结果：
- BFS 结束后，检查目标行星 $T$ 的两个可能状态：
  - 方案一 (偶数次传送)：如果 min_teleports[T][0] <= K，则 dist[T][0] 是一个有效解。
  - 方案二 (奇数次传送)：如果 min_teleports[T][1] <= K，则 dist[T][1] 是一个有效解。
- 最终答案是这两个有效解中的最小值。如果都无效，则无法到达。

该算法的时间和空间复杂度均为 $\mathcal{O}(N)$ ，满足题目要求。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const int INF = 1e9;

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

    int n, k, s, t, x, y;
    cin >> n >> k >> s >> t >> x >> y;
    --s; --t; // 0-indexed

    vector<vector<int>> dist(n, vector<int>(2, INF));
    vector<vector<int>> min_teleports(n, vector<int>(2, INF));
    queue<pair<int, int>> q;

    dist[s][0] = 0;
    min_teleports[s][0] = 0;
    q.push({s, 0});

    while (!q.empty()) {
        auto [u, layer] = q.front();
        q.pop();

        int current_dist = dist[u][layer];
        int current_tp = min_teleports[u][layer];

        // 1. Clockwise
        int v_cw = (u + x) % n;
        if (current_dist + 1 < dist[v_cw][layer]) {
            dist[v_cw][layer] = current_dist + 1;
            min_teleports[v_cw][layer] = current_tp;
            q.push({v_cw, layer});
        } else if (current_dist + 1 == dist[v_cw][layer]) {
            min_teleports[v_cw][layer] = min(min_teleports[v_cw][layer], current_tp);
        }

        // 2. Counter-clockwise
        int v_ccw = (u - y + n) % n;
        if (current_dist + 1 < dist[v_ccw][layer]) {
            dist[v_ccw][layer] = current_dist + 1;
            min_teleports[v_ccw][layer] = current_tp;
            q.push({v_ccw, layer});
        } else if (current_dist + 1 == dist[v_ccw][layer]) {
            min_teleports[v_ccw][layer] = min(min_teleports[v_ccw][layer], current_tp);
        }

        // 3. Teleport
        int v_tp = (u + n / 2) % n;
        int next_layer = 1 - layer;
        if (current_dist + 1 < dist[v_tp][next_layer]) {
            dist[v_tp][next_layer] = current_dist + 1;
            min_teleports[v_tp][next_layer] = current_tp + 1;
            q.push({v_tp, next_layer});
        } else if (current_dist + 1 == dist[v_tp][next_layer]) {
            min_teleports[v_tp][next_layer] = min(min_teleports[v_tp][next_layer], current_tp + 1);
        }
    }

    int ans = INF;
    if (min_teleports[t][0] <= k) {
        ans = min(ans, dist[t][0]);
    }
    if (min_teleports[t][1] <= k) {
        ans = min(ans, dist[t][1]);
    }

    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int s = sc.nextInt() - 1; // 0-indexed
        int t = sc.nextInt() - 1;
        int x = sc.nextInt();
        int y = sc.nextInt();

        int[][] dist = new int[n][2];
        int[][] minTeleports = new int[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            Arrays.fill(minTeleports[i], Integer.MAX_VALUE);
        }

        Queue<int[]> q = new LinkedList<>();

        dist[s][0] = 0;
        minTeleports[s][0] = 0;
        q.offer(new int[]{s, 0});

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0];
            int layer = curr[1];

            int currentDist = dist[u][layer];
            int currentTp = minTeleports[u][layer];

            // Moves array: {next_planet, is_teleport}
            int[][] moves = {
                {(u + x) % n, 0},
                {(u - y + n) % n, 0},
                {(u + n / 2) % n, 1}
            };

            for (int[] move : moves) {
                int v = move[0];
                int isTeleport = move[1];
                int nextLayer = layer ^ isTeleport;
                
                int newDist = currentDist + 1;
                int newTp = currentTp + isTeleport;

                if (newDist < dist[v][nextLayer]) {
                    dist[v][nextLayer] = newDist;
                    minTeleports[v][nextLayer] = newTp;
                    q.offer(new int[]{v, nextLayer});
                } else if (newDist == dist[v][nextLayer]) {
                    minTeleports[v][nextLayer] = Math.min(minTeleports[v][nextLayer], newTp);
                }
            }
        }
        
        long ans = Long.MAX_VALUE;
        if (minTeleports[t][0] <= k) {
            ans = Math.min(ans, dist[t][0]);
        }
        if (minTeleports[t][1] <= k) {
            ans = Math.min(ans, dist[t][1]);
        }

        if (ans == Long.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}

import sys
from collections import deque

def solve():
    n, k, s, t, x, y = map(int, sys.stdin.readline().split())
    s -= 1
    t -= 1

    INF = float('inf')
    dist = [[INF] * 2 for _ in range(n)]
    min_teleports = [[INF] * 2 for _ in range(n)]
    
    q = deque()

    dist[s][0] = 0
    min_teleports[s][0] = 0
    q.append((s, 0))

    while q:
        u, layer = q.popleft()
        
        current_dist = dist[u][layer]
        current_tp = min_teleports[u][layer]

        # Moves: (next_planet, is_teleport)
        moves = [
            ((u + x) % n, 0),
            ((u - y + n) % n, 0),
            ((u + n // 2) % n, 1)
        ]

        for v, is_teleport in moves:
            next_layer = layer ^ is_teleport
            new_dist = current_dist + 1
            new_tp = current_tp + is_teleport

            if new_dist < dist[v][next_layer]:
                dist[v][next_layer] = new_dist
                min_teleports[v][next_layer] = new_tp
                q.append((v, next_layer))
            elif new_dist == dist[v][next_layer]:
                min_teleports[v][next_layer] = min(min_teleports[v][next_layer], new_tp)

    ans = INF
    if min_teleports[t][0] <= k:
        ans = min(ans, dist[t][0])
    if min_teleports[t][1] <= k:
        ans = min(ans, dist[t][1])

    if ans == INF:
        print(-1)
    else:
        print(ans)

solve()

算法及复杂度

算法：带资源记录的广度优先搜索 (BFS)
时间复杂度： $\mathcal{O}(N)$ 。
- 我们构建了一个包含 $2N$ 个节点和大约 $6N$ 条边的双层图。
- 标准的 BFS 遍历这样一个图的复杂度是 $\mathcal{O}(V+E) = \mathcal{O}(N+N) = \mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。
- 主要空间开销来自于存储 dist 和 min_teleports 两个 $N \times 2$ 的数组，以及 BFS 使用的队列，其大小最坏情况下也与节点数 $N$ 成正比。