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复制说明你可以先顺时针移动 x2x2 颗行星到达编号 33再逆时针移动 y1y1 颗行星到达编号 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 vectorvectorint dist(n, vectorint(2, INF)); vectorvectorint min_teleports(n, vectorint(2, INF)); queuepairint, 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; }