Неявный граф

Граф не обязан лежать в памяти. Часто его выгоднее не строить вовсе — либо потому, что рёбра считаются по формуле, либо потому, что их квадратично много, а полезны единицы.

Рёбра по формуле

Даны точки на плоскости, стоимость перехода между двумя точками — квадрат расстояния между ними. Найти самый дешёвый маршрут из $s$ в $t$.

Граф полный: $n^2$ рёбер. При $n = 10^4$ матрица смежности из long long — 800 мегабайт, не влезает.

Но Дейкстра за $O(n^2)$ рёбра и не хранит. В момент перебора соседей она считает вес:

used[v] = 1;
for (int u = 0; u < n; u++) {
    if (used[u]) continue;
    long long dx = x[v] - x[u], dy = y[v] - y[u];
    long long c = dx * dx + dy * dy;
    if (d[v] + c < d[u]) d[u] = d[v] + c;
}

Память — $O(n)$, время — $O(n^2)$, ровно как у обычной версии. Здесь выбор реализации Дейкстры диктуется не разреженностью графа, а тем, что рёбер физически нет.

Кстати о постановке: если бы стоимость была равна расстоянию, а не его квадрату, ответом был бы прямой отрезок из $s$ в $t$ и никакой граф не понадобился бы. Квадрат ломает неравенство треугольника — путь выгодно дробить, — и задача становится содержательной.

Рёбер квадрат, полезных — линия

На прямой длины $10^9$ стоят $s$ и $t$. В точке $x_i$ есть телепорт силы $d_i$: из $x_i$ мгновенно попадаешь в $x_i - d_i$ или $x_i + d_i$. Ещё можно идти пешком, единица длины — единица времени. Телепортов до $10^5$.

Первое: вершин не $10^9$, а мало. Значимы только точки $s$, $t$, все $x_i$ и все $x_i \pm d_i$ — не больше $3k + 2$ штук. Остальную прямую проходят насквозь. Дальше — сжатие координат.

Второе, и это главное: не соединяйте все пары. Ребро «из этой точки в далёкую за расстояние между ними» бесполезно — тот же путь набирается переходами между соседними точками. Достаточно соединить каждую точку с соседом слева и справа.

sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto id = [&](long long v) {
    return int(lower_bound(xs.begin(), xs.end(), v) - xs.begin());
};

int n = xs.size();
vector<vector<pair<int, long long>>> g(n);
for (int i = 0; i + 1 < n; i++) {          // пешком между соседними точками
    long long c = xs[i + 1] - xs[i];
    g[i].push_back({i + 1, c});
    g[i + 1].push_back({i, c});
}
for (auto [x, d] : teleports) {            // телепорты — рёбра веса 0
    int a = id(x);
    g[a].push_back({id(x - d), 0});
    g[a].push_back({id(x + d), 0});
}

Рёбер стало $O(k)$ вместо $O(k^2)$, и дальше — обычная Дейкстра.

Проверено: на двух тысячах случайных наборов телепортов ответ на разреженном графе совпал с ответом на полном графе, где проведены рёбра между всеми парами точек.

Работает это ровно потому, что «пешком» — метрика на прямой: длина прохода из $i$ в $j$ равна сумме длин соседних отрезков между ними. Прежде чем выбрасывать рёбра, убедитесь, что такое разложение есть; на плоскости с препятствиями его уже нет.

Веса на вершинах

В каждом городе своя цена бензина; чтобы выехать из города, надо в нём заправиться. Нужен самый дешёвый маршрут.

Веса на вершинах превращаются в веса на рёбрах: проезд по ребру $v \to u$ стоит столько, сколько стоит бензин в $v$. Неориентированное ребро становится двумя ориентированными с разными весами:

g[v].push_back({u, cost[v]});
g[u].push_back({v, cost[u]});

Строится на этапе чтения, дальше — обычная Дейкстра. Заправка в конечном городе не нужна, и она автоматически не считается: последнее ребро оплачено предпоследним городом.

Ограничения превращаются в фильтр рёбер

У каждой дороги есть время проезда и предельная грузоподъёмность. Машина весит 3 тонны, каждая кружка — 100 граммов; надо провезти как можно больше кружек из вершины 1 в вершину $n$ за сутки.

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

Проверка для фиксированного $k$: вес равен $3\,000\,000 + 100k$ граммов, выбрасываем все рёбра со слишком малой грузоподъёмностью, запускаем Дейкстру и смотрим, укладываемся ли в 1440 минут.

Граф здесь тоже неявный: он свой для каждого $k$, и строить его заново незачем — достаточно пропускать негодные рёбра прямо в цикле по соседям.

Другие задачи на связку бинпоиска с обходом — в статье бинпоиск и кратчайшие пути.