68. Метро

Схема метро состоит из n  станций, размещенных на l линиях. Каждая станция принадлежит одной или более линиям (в этом случае на станции можно выполнить пересадку на любою из линий, которые через нее проходят). Каждая линия состоит из двух или более станций и пересекается хотя бы с одной другой линией. Схема метро связана.

Движение между двумя соседними станциями одной линии можно производить в любом направлении на протяжении 2 минут; на пересадку с линии на линию в пределах одной станции тратится 1 минута. Любыми другими затратами времени можно пренебречь.

Найти минимальное время, необходимое для того, чтобы менеджеру фирмы “Диез-продукт” добраться от станции a к зданию офиса компании, расположенного вблизи станции b.

Вход. В первой строке заданы два натуральных числа n и l (1 ≤ l ≤ 10). В следующих l строках записаны последовательные номера станций каждой из линий метро. В последней строке указаны номер и линия начальной и конечной станций. Все числа натуральные и не превышают 70.

Выход. Вывести минимальное время движения между указанными станциями.

Пример входа	Пример выхода
7 3 2 1 3 6 1 4 5 5 7 2 1 7 3	10

РЕШЕНИЕ

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

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

Кратчайшее расстояние от источника до вершины v, принадлежащей линии l, храним в dist[v][l], где 1 ≤ v ≤ 70, 1 ≤ l ≤ 10. Граф храним в виде списков смежности. Вместе с направлением и стоимостью ребра храним номер линии метро, которой принадежит вершина куда направлено ребро.

Стартуем со станции s, находящейся на линии line1. Ответ на задачу – минимальная стоимость, за которую можно добраться до вершины f на линии line2. При движении между вершинами следует совершить проверку: если вершины принадлежат разным линиям, то следует добавить 1 (совершить пересадку).

При помощи алгоритма Дейкстры находим кратчайшее расстояния из сосотяния (s, line1) в (f, line2).

Пример

Граф, приведенный в примере, имеет вид:

Для передвижения со станции 2 на станцию 7 необходимо проехать 4 перегона (8 минут) и совершить 2 пересадки (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;

priority_queue<node, vector<node> > pq;

Заносим в очередь структуру node, содержащую начальную вершину s на линии line1. Стоимость попадания в начальную вершину равна 0.

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 (i = 0; i < g[v].size(); i++)

{

Имеется ребро v – to стоимостью w, принадлежащее линии l2.

int to = g[v][i].to;

int w = g[v][i].cost;

int l2 = g[v][i].line;

Если двигаться в to по ребру v – to, то стоимость составит cost + w.

int tot_cost = cost + w;

Если линии у вершин v и to разные, то следует совершить пересадку с линии l1 на линию l2.

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

Если движение по ребру v – 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]);