Подорож (Розбір)

Побудуємо два графи: граф доріг $g[0]$ і граф стежок $g[1]$. Далі обчислимо найкоротші відстані від села Домніно $t$ до всіх сіл:

• За картою Стефана: $d[0][i]$ — мінімальна відстань від $t$ до села $i$;

• За картою Костянтина: $d[1][i]$ — мінімальна відстань від $t$ до села $i$;

Потім розглянемо граф, вершинами якого є пари (v, parity):

• $v$ — номер села;

• parity = 0 (ніч, пересування по дорогах), parity = 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 \oplus 1) — перехід в протилежну фазу.

• Оновлюємо значення dp[type][v]:

Таким чином, ми обираємо найкращий наступний хід, який призводить до максимальної сумарної довжини шляху. Це аналог стандартного пошуку найдовшого шляху в DAG (орієнтованому ациклічному графі), де напрямок ребер визначається зменшенням найкоротшої відстані.

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

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

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

Оголосимо константи.

#define INF 2e18
#define MAXN 1005

Оголосимо використовувані структури даних:

• $g[0]$ і $g[1]$ — списки суміжності для графів доріг і стежок відповідно.

• $d[0]$ і $d[1]$ — найкоротші відстані від села Домніно $t$ до всіх інших сіл.

• $dp[0]$ і $dp[1]$ — максимальна довжина шляху від вершини $v$ до $t$, якщо стартувати з $v$ по дорозі (type = 0) або по стежці (type = 1).

• $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 = 0). Якщо при такому чергуючому русі виникає можливість потрапити в цикл, функція повертає $-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 \oplus 1] вже знаходиться в процесі обходу (позначена як "сіра"), значить, виявлено цикл — повертаємо $-1$.

      if (used[type ^ 1][to] == 1)
      {
        cout << -1 << endl;
        exit(0);
      }

Якщо вершина $to$ в графі g[type \oplus 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]);