Метро (Розбір)

Найкоротша відстань від джерела до вершини $v$, що належить до лінії $l$, зберігаємо в dist[v][l], де 1 \le v \le 70, 1 \le l \le 10. Граф представляється у вигляді списків суміжності. Для кожного ребра, крім напрямку і вартості, додатково зберігається номер лінії метро, до якої належить вершина, до якої це ребро веде.

Алгоритм починається зі станції $s$, розташованої на лінії $line1$. Шукана величина — мінімальна вартість маршруту, за яку можна дістатися до станції $f$, що знаходиться на лінії $line2$.

При переході між вершинами необхідно перевіряти, чи належать вони одній лінії: якщо лінії різні, до вартості додається $1$ (пересадка між лініями).

За допомогою алгоритму Дейкстри знаходимо найкоротшу відстань із стану (s, line1) до стану (f, line2).

Приклад

У наведеному прикладі потрібно знайти найкоротший маршрут від станції $2$ на лінії $1$ до станції $7$ на лінії $3$.

• Йдемо по лінії $1$ від станції $2$ до станції $1$: $2$ хвилини.

• Здійснюємо пересадку на станції $1$ з лінії $1$ на лінію $2$: $1$ хвилина.

• Йдемо по лінії $2$ від станції $1$ до станції $5$: $4$ хвилини.

• Здійснюємо пересадку на станції $5$ з лінії $2$ на лінію $3$: $1$ хвилина.

• Йдемо по лінії $3$ від станції $5$ до станції $7$: $2$ хвилини.

Отже, весь шлях займе $10$ хвилин.

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

Кількість вершин у графі не більше MAX = 71. Кількість ліній не більше LINES = 11.

#define MAX 71
#define LINES 11

Найкоротші відстані від джерела до вершини $v$, що належить лінії $l$, зберігаємо в dist[v][l]. Оголосимо масив для зберігання найкоротших відстаней.

int dist[MAX][LINES];

Структура node містить інформацію про ребро:

• $to$ — напрямок ребра;

• $cost$ — вартість ребра;

• $line$ — якій лінії метро ребро належить;

struct node
{
  int to, cost, line;
  node(int to, int cost, int line) : to(to), cost(cost), line(line) {}
};

Структура node також використовується в черзі з пріоритетами, де

• $to$ — поточна вершина;

• $cost$ — мінімальна вартість проїзду до вершини $to$ (на лінії $line$);

• $line$ — номер лінії метро, на якій знаходиться вершина $to$;

В черзі з пріоритетами вершини впорядковуються за зростанням вартості проїзду.

bool operator< (node a, node b)
{
  return a.cost > b.cost;
}

Оголосимо список суміжності для представлення графа.

vector<vector<node> > g;

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &n, &l);
g.resize(n + 1);

Читаємо $i$-ту лінію метро. Час руху між сусідніми станціями $u$ та $v$ дорівнює $2$.

for (i = 1; i <= l; i++)
{

Читаємо станцію $u$ — першу станцію $i$-ої лінії метро. За станцією $u$ слідує станція $v$.

  scanf("%d ", &u);
  while (scanf("%d%c", &v, &ch))
  {

Рух між станціями можливий в обох напрямках, при цьому вартість ребра дорівнює $2$.

    g[u].push_back(node(v, 2, i));
    g[v].push_back(node(u, 2, i));
    u = v;

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

    if (ch == '\n') break;
  }
}

Ініціалізуємо масив для зберігання найкоротших відстаней.

for (i = 1; i <= n; i++)
for (j = 1; j <= l; j++)
  dist[i][j] = 2000000000;

Читаємо інформацію про початкову та кінцеву станцію. Для кожної станції задається лінія, якій вона належить.

scanf("%d %d %d %d", &s, &line1, &f, &line2);

Стартуємо зі станції $s$, що знаходиться на лінії $line1$.

dist[s][line1] = 0;

Заносимо в чергу структуру node, що містить початкову вершину $s$ на лінії $line1$. Вартість досягнення початкової вершини дорівнює $0$.

priority_queue<node, vector<node> > pq;
pq.push(node(s, 0, line1)); // (v, cost, line)
while (!pq.empty())
{

Вибираємо з черги вершину $v$ з найменшою вартістю.

  int cost = pq.top().cost;
  int v = pq.top().to;
  int l1 = pq.top().line;
  pq.pop(); // dist[v][l1] = cost

Перебираємо всі вершини, суміжні з $v$.

  for (auto edge: g[v])
  {

Розглядаємо ребро v \to to із вартістю $w$, що належить лінії $l2$.

    int to = edge.to;
    int w = edge.cost;
    int l2 = edge.line;

Якщо рухатися по ребру v \to to, то вартість маршруту складе cost + w.

    int tot_cost = cost + w;

Якщо вершини $v$ та $to$ належать різним лініям, необхідно здійснити пересадку з лінії $l1$ на лінію $l2$.

    if (l1 != l2) tot_cost += 1;

Якщо рух по ребру v \to to покращує поточне значення, оновлюємо dist[to][l2] і поміщаємо вершину $to$ в чергу (вартість її досягнення складає $tot\_cost$ і вона знаходиться на лінії $l2$).

    if (tot_cost < dist[to][l2])
    {
      dist[to][l2] = tot_cost;
      pq.push(node(to, tot_cost, l2));
    }
  }
}

Виводимо відповідь — мінімальна вартість маршруту до вершини $f$ на лінії $line2$.

printf("%d\n", dist[f][line2]);