Метро

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

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

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

При помощи алгоритма Дейкстры находим кратчайшее расстояния из состояния ( $s$ , $l in e 1$ ) в ( $f$ , $l in e 2$ ).

Пример

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

Для передвижения со станции 2 на станцию 7 необходимо проехать 4 перегона (8 минут) и совершить 2 пересадки (2 минуты). Итого время движения займет 10 минут.

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

Количество вершин в графе не более MAX = 71. Количество линий не более LINES = 11.

#define MAX 71
#define LINES 11

int dist[MAX][LINES];

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

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

vector<vector<node>> g;

// Чтение входных данных и инициализация графа

for (i = 1; i <= l; i++)
{
    scanf("%d ", &u);
    while (scanf("%d%c", &v, &ch))
    {
        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);

// Алгоритм Дейкстры
dist[s][line1] = 0;
priority_queue<node, vector<node>> pq;
pq.push(node(s, 0, line1)); // (v, cost, line)

while (!pq.empty())
{
    int cost = pq.top().cost;
    int v = pq.top().to;
    int l1 = pq.top().line;
    pq.pop();

    for (i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i].to;
        int w = g[v][i].cost;
        int l2 = g[v][i].line;
        int tot_cost = cost + w;
        if (l1 != l2) tot_cost += 1;
        if (tot_cost < dist[to][l2])
        {
            dist[to][l2] = tot_cost;
            pq.push(node(to, tot_cost, l2));
        }
    }
}

// Вывод ответа
printf("%d\n", dist[f][line2]);