HJ164 太阳系DISCO
- 题目
- 题解(7)
- 讨论(12)
- 排行
中等 通过率：33.93% 时间限制：1秒 空间限制：256M
知识点广度优先搜索(BFS)
校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
在一个平行世界的太阳系中，所有行星恰好构成一个长度为 nn 的环，按顺时针依次编号为 1,2,…,n1,2,…,n。相邻两颗行星间距离相等，且保证 nn 为偶数。
你位于编号为 aa 的行星，目标是到达编号为 bb 的行星。你可以执行以下三种操作，每次操作均消耗 11 个单位时间：
∙ ∙顺时针移动 xx 颗行星；
∙ ∙逆时针移动 yy 颗行星；
∙ ∙发动一次传送技能（最多可使用 kk 次），将你顺时针移动 n22n 颗行星，即跳到正对面的那颗行星。
请你计算，从 aa 行星移动到 bb 行星的最少时间；若无论如何都无法到达，则输出 −1−1。
输入描述：
在一行上输入 66 个整数 n,k,a,b,x,yn,k,a,b,x,y，含义分别为：
∙ ∙n(2≦n≦2×105)n(2≦n≦2×105)——行星数量，且 nn 为偶数；
∙ ∙k(0≦k≦2×105)k(0≦k≦2×105)——技能可使用的最大次数；
∙ ∙a,b(1≦a,b≦n)a,b(1≦a,b≦n)——起点与终点的编号；
∙ ∙x,y(1≦x,y≦n)x,y(1≦x,y≦n)——每次普通移动的距离。
输出描述：
输出一个整数，表示最少所需时间；若无法到达，则输出 −1−1。
示例1
输入：
4 0 1 2 2 1
复制输出：
2
复制说明：
你可以先顺时针移动 x=2x=2 颗行星到达编号 33，再逆时针移动 y=1y=1 颗行星到达编号 22，共耗时 22。
示例2
输入：
4 114514 1 3 1 1
复制输出：
1
复制
示例3
输入：
4 114514 1 2 2 2
复制输出：
-1
#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; }