2267. Путешествие

Армия Речи Посполитой движется из города Костромы в деревню Домнино. Во главе армии стоят два гетмана – Стефан и Константин.

Стефан приобрел карту Костромской области, и каждую ночь он ведет армию от одной деревни к другой по одной из указанных дорог. Константин же раздобыл карту секретных троп, и каждый день он ведет армию по одной из этих троп. Перед каждым переходом каждый из гетманов спрашивает у проводника Ивана Сусанина, какой маршрут лучше выбрать.

На карте у Стефана указана длина каждой дороги, поэтому он знает минимальные расстояния между любой деревней и деревней Домнино по своей карте. Аналогично, Константин знает кратчайшие расстояния до Домнино, если следовать по тропам согласно его карте.

Иван Сусанин, будучи тайным агентом, не хочет разоблачить себя. Поэтому каждый раз он выбирает дорогу (для Стефана) и тропу (для Константина) так, чтобы кратчайшее расстояние до деревни Домнино, согласно карте того гетмана, который задает вопрос, строго уменьшалось.

Помогите Ивану найти самый длинный возможный путь до деревни Домнино.

Вход. Первая строка содержит три целых числа n, s и t (2 ≤ n ≤ 1000, 1 ≤ s, t ≤ n) – количество деревень в Костромской области, а также номера начальной деревни и деревни Домнино. Деревни пронумерованы числами от 1 до n. Начальная деревня и деревня Домнино различны.

Далее следуют два блока, каждый из которых задает карту: первый блок – карту Стефана, второй — карту Константина.

Первая строка каждого блока содержит целое число m (n – 1 ≤ m ≤ 10⁵) – количество дорог/троп между деревнями. Каждая из следующих m строк содержит три целых числа a, b и l, описывающих дорогу или тропу между деревнями a и b длиной l (1 ≤ a, b ≤ n, 1 ≤ l ≤ 10⁶).

Армия может двигаться в любом направлении по дорогам и тропам. Известно, что по карте каждого гетмана можно добраться из любой деревни в любую. Армия стартует вечером из начальной деревни, продвигаясь по одной дороге каждую ночь и по одной тропе каждый день.

Выход. Выведите длину самого длинного пути, по которому Иван Сусанин может водить армию Речи Посполитой, пока она не достигнет деревни Домнино (с учетом дорог и троп). Если Иван может водить армию бесконечно, не достигая Домнино, выведите “-1”.

Пример входа 1	Пример выхода 1
5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2	-1
Пример входа 2	Пример выхода 2
3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10	20

РЕШЕНИЕ

графы – алгоритм Дейкстры

Анализ алгоритма

Построим два графа: граф дорог g[0] и граф троп g[1]. Далее вычислим кратчайшие расстояния от деревни Домнино t до всех деревень:

· По карте Стефана: d[0][i] – минимальное расстояние от t до деревни i;

· По карте Константина: d[1][i] – минимальное расстояние от t до деревни i;

Далее рассматриваем граф, вершинами которого являются пары (v, parity):

· v – номер деревни;

· parity – 0 (ночь, дорога), 1 (день, тропа)

Армия стартует вечером из начальной деревни, двигаясь ночью по дороге (parity = 0). Запускаем поиск в глубину из вершины (s, 0) по следующим правилам:

· из (v, 0) (ночь) идём по дороге в (u, 1), если d[0][u] < d[0][v];

· из (v, 1) (день) идём по тропе в (u, 0), если d[1][u] < d[1][v].

Находясь в состоянии (v, parity), мы делаем перебор только допустимых путей, то есть таких, где расстояние до Домнино строго уменьшается. И среди них находим максимально длинный путь.

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

При поиске в глубину будем поддерживать динамику:

· dp[type][v] – максимальная длина пути от v до t, начиная с типа type.

Для каждого допустимого перехода:

· Рекурсивно вызываем dfs(to, type ^ 1) – противоположная фаза.

· Обновляем dp[type][v]:

dp[type][v] = max(dp[type][v], dp[type ^ 1][to] + weight);

Таким образом мы выбираем наилучший следующий ход, приводящий к максимальной суммарной длине пути. Это аналог стандартного “поиска самого длинного пути в DAG (ориентированном ациклическом графе)”, где направление задаётся уменьшением кратчайшего расстояния.

Движение разрешено только по рёбрам, ведущим к вершинам с меньшим расстоянием до Домнино. Однако в задаче есть два графа (два типа рёбер: дороги и тропы), и переходы между ними чередуются – ночь (дорога), день (тропа), ночь, день, ... . И вот именно из-за чередования карт (дорог и троп) может возникнуть цикл между вершинами, даже несмотря на то, что в каждом отдельном графе (по одной карте) движение идёт по убывающему расстоянию.

Если при поиске в глубину мы снова попадаем в вершину, которая уже находится в стеке обработки, значит, обнаружен цикл.

Реализация алгоритма

Объявим константы.

#define INF 2e18

#define MAXN 1005

Объявим используемые структуры данных:

· g[0] и g[1] – соответственно списки смежностей для графов дорог и троп.

· d[0] и d[1] – соответственно кратчайшие расстояния от деревни Домнино t до остальных деревень.

· dp[0] и dp[1] – максимальная длина пути от v до t, если стартовать из v соответственно по дороге или тропе.

· used[0] и used[1] – метки вершин при обходе в глубину соответственно для графов дорог и троп.

vector<pair<int, int>> g[2][MAXN];

long long d[2][MAXN];

long long dp[2][MAXN];

int used[2][MAXN];

Функция dijkstra вычисляет кратчайшие расстояния от деревни Домнино t до остальных деревень по дорогам (type = 0) или тропам (type = 1).

void dijkstra(int type)

{

for (int i = 1; i <= n; i++)

d[type][i] = INF;

d[type][t] = 0;

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

pq.push({ 0, t });

while (!pq.empty())

{

pair<long long, int> top = pq.top();

pq.pop();

long long dist = top.first;

int v = top.second;

if (dist > d[type][v]) continue;

for (auto edge : g[type][v])

{

int to = edge.first;

int w = edge.second;

if (d[type][to] > d[type][v] + w)

{

d[type][to] = d[type][v] + w;

pq.push({ d[type][to], to });

}

}

}

}

Функция dfs совершает поиск в глубину и находит самый длинный путь по чередующимся картам, стартуя с деревни v по дороге (type = 0) или тропе (type = 1). Если движение по чередующимся картам может попасть в цикл, возвращаем -1.

void dfs(int v, int type)

{

Вершина v графа g[type] становится серой.

used[type][v] = 1;

Инициализируем динамику.

dp[type][v] = 0;

Перебираем ребра, исходящие из вершины v графа g[type].

for (auto edge : g[type][v])

{

int to = edge.first;

int weight = edge.second;

Двигаться из вершины v в вершину to можно, только если расстояние от to до Домнино меньше расстояния от v до Домнино.

if (d[type][to] < d[type][v])

{

Если мы уже посещали вершину to графа g[type ^ 1] (движение происходит в вершину to в другой карте), то найден цикл. Возвращаем -1.

if (used[type ^ 1][to] == 1)

{

cout << -1 << endl;

exit(0);

}

Если вершина to графа g[type ^ 1] еще не посещена, то продолжаем из нее поиск в глубину.

if (used[type ^ 1][to] == 0)

dfs(to, type ^ 1);

Пересчитываем динамику, выбирая самый длинный путь из вершины v в графе g[type] в Домнино.

dp[type][v] = max(dp[type][v], dp[type ^ 1][to] + weight);

}

}

Вершина v графа g[type] становится черной.

used[type][v] = 2;

}

Основная часть программы. Читаем входные данные. Строим графы дорог и троп.

scanf("%d %d %d", &n, &s, &t);

scanf("%d", &m1);

for (i = 0; i < m1; i++)

{

scanf("%d %d %d", &a, &b, &len);

g[0][a].push_back({ b, len });

g[0][b].push_back({ a, len });

}

scanf("%d", &m2);

for (i = 0; i < m2; i++)

{

scanf("%d %d %d", &a, &b, &len);

g[1][a].push_back({ b, len });

g[1][b].push_back({ a, len });

}

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

dijkstra(0);

dijkstra(1);

При помощи поиска в глубину находим самый длинный путь по чередующимся картам, стартуя с деревни s по дороге.

dfs(s, 0);

Выводим ответ. Стартуем с деревни s по дороге.

printf("%lld\n", dp[0][s]);