Как найти кратчайший путь чётной (или кратной k) длины через расширение состояний?
Задача: дойти из s в t так, чтобы число рёбер пути было чётным (граф невзвешенный). Обычный BFS даёт минимум рёбер, но не различает чётность. Иногда кратчайший чётный путь длиннее кратчайшего вообще. Как такое решать?
2 ответа
Расширяем состояние: вершина становится парой (вершина, чётность пройденных рёбер). Дублируем граф на два слоя — «чётный» и «нечётный», и каждое ребро переключает слой. BFS по этому удвоенному графу.
// dist[v][p]: p=0 чётное число рёбер, p=1 нечётное
vector<array<int,2>> dist(n, {-1, -1});
queue<pair<int,int>> q;
dist[s][0] = 0; q.push({s, 0});
while (!q.empty()) {
auto [v, p] = q.front(); q.pop();
for (int u : g[v]) {
int np = p ^ 1; // ребро меняет чётность
if (dist[u][np] == -1) {
dist[u][np] = dist[v][p] + 1;
q.push({u, np});
}
}
}
// кратчайший чётный путь до t = dist[t][0]
Сложность O(V + E) (граф вырос вдвое — константа). dist[t][0] — кратчайший путь чётной длины, dist[t][1] — нечётной.
Обобщение: для «длина кратна k» состояние = (вершина, длина mod k), граф растёт в k раз, переход прибавляет 1 к остатку. Тот же приём решает задачи вроде «дойти ровно за время, делящееся на светофорный цикл» или «чередовать типы рёбер». Если рёбра взвешенные и остаток считается по сумме весов mod k — берём Дейкстру вместо BFS по тем же расширенным состояниям (v, sum mod k).