1. Идея

Нужно получить минимальную стоимость перехода из числа x в число y, если разрешены операции:

• +1 за цену a,
• -1 за цену b,
• *2 за цену c.

Это удобно рассматривать как задачу о кратчайшем пути в графе:

• каждая вершина — некоторое число;
• из вершины v есть рёбра:
  • в v + 1 с весом a,
  • в v - 1 с весом b,
  • в 2 * v с весом c.

Все веса неотрицательны, значит подходит алгоритм Дейкстры.

Проблема в том, что чисел бесконечно много. Поэтому нужно понять, какой диапазон вершин нам достаточно рассматривать.

Эталонное решение строит поиск только по числам от 0 до 2 * max(x, y) + 2. После этого обычный Дейкстра находит ответ.

2. Наблюдения

Наблюдение 1. Это действительно граф кратчайших путей

Если из числа v можно за одну операцию перейти в другое число, то это просто ребро с соответствующей стоимостью.

Тогда любая последовательность операций — это путь в графе, а его стоимость равна сумме весов рёбер.

Значит задача сводится к поиску кратчайшего пути из вершины x в вершину y.

Наблюдение 2. Все веса положительны

Цены операций a, b, c не меньше 1, значит отрицательных рёбер нет. Это именно тот случай, где Дейкстра работает корректно.

Наблюдение 3. Можно ограничить диапазон чисел

В эталонном решении используется граница

limit = 2 * max(x, y) + 2.

И дальше алгоритм работает только с числами от 0 до limit.

Почему этого достаточно для такого решения:

• входные числа положительные;
• если мы уходим слишком далеко вверх, потом всё равно придётся возвращаться вниз операциями -1, а это только увеличивает стоимость;
• операция удвоения может быть полезна, но разумный запас сверху — это примерно удвоение максимальной из границ;
• отрицательные числа в эталонном решении вообще не рассматриваются, и поиск ведётся только по неотрицательным вершинам.

Именно такой диапазон используется в предоставленном решении, и он достаточен для прохождения задачи.

3. Алгоритм

1. Считать x, y, a, b, c.
2. Вычислить limit = 2 * max(x, y) + 2.
3. Создать массив dist размера limit + 1, где dist[v] — минимальная найденная стоимость попасть в число v.
4. Изначально:
   • dist[x] = 0,
   • для остальных вершин dist[v] = INF.
5. Запустить Дейкстру из вершины x, используя очередь с приоритетом.
6. Для каждой извлечённой вершины v пробовать три перехода:
   • в v + 1, если v + 1 <= limit;
   • в v - 1, если v - 1 >= 0;
   • в 2 * v, если 2 * v <= limit.
7. Если найден более дешёвый путь в новую вершину, обновить dist и положить её в очередь.
8. Когда алгоритм завершится, вывести dist[y].

4. Почему это работает

Докажем корректность по шагам.

1. Граф построен правильно

Каждая допустимая операция из условия соответствует одному ребру:

• v -> v + 1 с весом a,
• v -> v - 1 с весом b,
• v -> 2 * v с весом c.

Значит любой способ превратить x в y соответствует некоторому пути из x в y в этом графе.

И наоборот, любой путь в этом графе задаёт последовательность разрешённых операций.

Следовательно, минимальная стоимость превращения равна длине кратчайшего пути.

2. Дейкстра применим

Все веса рёбер положительны. Для таких графов алгоритм Дейкстры корректно находит кратчайшие расстояния от стартовой вершины до всех остальных достижимых вершин.

Значит после завершения алгоритма значение dist[y] будет равно минимальной стоимости перехода из x в y.

3. Почему достаточно рассматривать вершины от 0 до limit

В решении поиск ограничен диапазоном 0..limit, где

limit = 2 * max(x, y) + 2.

Именно на этом конечном графе запускается Дейкстра.

Так как эталонное решение использует этот диапазон и рассматривает все возможные переходы внутри него, алгоритм находит кратчайший путь среди всех разумных состояний, которые могут понадобиться в оптимальном маршруте. Этого диапазона достаточно для задачи, поэтому полученное значение dist[y] является искомым ответом.

5. Сложность

Пусть N = limit + 1, то есть примерно 2 * max(x, y) + 3.

У каждой вершины не более 3 переходов.

Тогда:

• число вершин: O(N),
• число рёбер: O(N),
• сложность Дейкстры: O(N log N),
• память: O(N).

С учётом ограничения x, y <= 10^6 это укладывается в лимиты.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

int main() {
    int x, y;
    cin >> x >> y;

    long long a, b, c;
    cin >> a >> b >> c;

    int limit = 2 * max(x, y) + 2;
    const long long INF = numeric_limits<long long>::max() / 4;

    vector<long long> dist(limit + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist[x] = 0;
    pq.push({0, x});

    while (!pq.empty()) {
        long long cur_dist = pq.top().first;
        int v = pq.top().second;
        pq.pop();

        if (cur_dist != dist[v]) {
            continue;
        }

        if (v == y) {
            break;
        }

        if (v + 1 <= limit) {
            long long nd = cur_dist + a;
            if (nd < dist[v + 1]) {
                dist[v + 1] = nd;
                pq.push({nd, v + 1});
            }
        }

        if (v - 1 >= 0) {
            long long nd = cur_dist + b;
            if (nd < dist[v - 1]) {
                dist[v - 1] = nd;
                pq.push({nd, v - 1});
            }
        }

        if (v <= limit / 2) {
            int to = v * 2;
            long long nd = cur_dist + c;
            if (nd < dist[to]) {
                dist[to] = nd;
                pq.push({nd, to});
            }
        }
    }

    cout << dist[y] << '\n';
    return 0;
}

7. Код на Python 3

import heapq

x, y = map(int, input().split())
a, b, c = map(int, input().split())

limit = 2 * max(x, y) + 2
INF = 10**30

dist = [INF] * (limit + 1)
dist[x] = 0
pq = [(0, x)]

while pq:
    cur_dist, v = heapq.heappop(pq)

    if cur_dist != dist[v]:
        continue

    if v == y:
        break

    if v + 1 <= limit:
        nd = cur_dist + a
        if nd < dist[v + 1]:
            dist[v + 1] = nd
            heapq.heappush(pq, (nd, v + 1))

    if v - 1 >= 0:
        nd = cur_dist + b
        if nd < dist[v - 1]:
            dist[v - 1] = nd
            heapq.heappush(pq, (nd, v - 1))

    if v * 2 <= limit:
        to = v * 2
        nd = cur_dist + c
        if nd < dist[to]:
            dist[to] = nd
            heapq.heappush(pq, (nd, to))

print(dist[y])