Codeforces 520B Two Buttons：SPFA / BFS 求最短操作步數

題目大意

初始數 n，目標 m（1 ≤ n, m ≤ 10⁴）。兩操作：紅鍵 ×2，藍鍵 -1（數字必須保持正數）。求最少操作次數讓 n 變為 m。

圖模型與 SPFA

將每個正整數視為節點，邊：u → 2u（權 1）、u → u-1（權 1，u>1）。求 n 到 m 的最短路。因邊權均為 1，實際上 BFS 即可，但 SPFA 也能通過。

優化觀察

• 若 n ≥ m，只能做 -1 操作，答案直接為 n - m。
• 搜索上界：2m 足夠（超過 2m 只會增加步數）。
• BFS 更簡單高效：O(上界) 時間。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20020;

int main() {
    int n, m; cin >> n >> m;
    if (n >= m) { cout << n - m << '\n'; return 0; }
    vector dist(MAXN, -1);
    queue q;
    dist[n] = 0; q.push(n);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == m) break;
        int v1 = u * 2;
        if (v1 < MAXN && dist[v1] == -1) { dist[v1] = dist[u] + 1; q.push(v1); }
        int v2 = u - 1;
        if (v2 > 0 && dist[v2] == -1) { dist[v2] = dist[u] + 1; q.push(v2); }
    }
    cout << dist[m] << '\n';
    return 0;
}

複雜度

• BFS：O(MAXN) ≈ 2×10⁴，極快。
• 空間：O(MAXN)。

範例

n=4, m=6: 4 →(藍) 3 →(紅) 6  步數 2
n=10, m=1: 僅 -1，步數 9

本題展示了在隱式圖上進行 BFS 求最短路的經典技巧，並利用問題特性（n ≥ m 直接算）大幅優化。