Маршруты одинаковой длины — разбор задачи

1. Идея

Так как каждый перегон имеет одинаковую стоимость, равную 1, кратчайшие расстояния в таком графе удобнее всего искать обходом в ширину, то есть BFS.

Но здесь нужно найти не только длину кратчайшего пути от 1 до n, но и количество таких путей.

Поэтому вместе с массивом расстояний будем хранить ещё один массив:

• dist[v] — минимальное число перегонов от станции 1 до станции v;
• ways[v] — количество кратчайших маршрутов до станции v.

Во время BFS:

• если вершина to найдена впервые, значит мы пришли в неё кратчайшим способом;
• если в вершину to можно попасть ещё одним способом той же минимальной длины, нужно добавить число путей.

2. Наблюдения

Наблюдение 1

В невзвешенном графе BFS находит кратчайшие расстояния от стартовой вершины до всех остальных.

Это работает потому, что сначала обрабатываются все вершины на расстоянии 0, затем на расстоянии 1, потом на расстоянии 2 и так далее.

Наблюдение 2

Если из вершины v есть ребро в to, и dist[to] == -1, то мы нашли вершину to впервые. Тогда:

• dist[to] = dist[v] + 1
• ways[to] = ways[v]

Почему именно так? Потому что пока найден только один тип кратчайших путей в to: все кратчайшие пути в v, а потом один шаг в to.

Наблюдение 3

Если dist[to] == dist[v] + 1, значит мы нашли ещё один кратчайший способ попасть в to.

Тогда надо сделать:

• ways[to] += ways[v]

Потому что каждый кратчайший путь в v, продолженный ребром v -> to, даёт новый кратчайший путь в to.

Наблюдение 4

В задаче разрешены несколько перегонов между одной и той же парой станций.

Это важно: такие перегоны считаются разными, потому что маршруты различаются хотя бы одним перегоном. Значит, каждое ребро из списка смежности нужно обрабатывать отдельно, ничего удалять или "сжимать" нельзя.

Наблюдение 5

Если n = 1, то путь из 1 в 1 уже существует:

• длина равна 0,
• количество таких маршрутов равно 1.

Наш алгоритм автоматически это учтёт.

3. Алгоритм

1. Считать n и m.
2. Построить список смежности неориентированного графа.
3. Создать массивы:
   • dist размера n + 1, заполненный значением -1;
   • ways размера n + 1, заполненный нулями.
4. Запустить BFS из вершины 1:
   • dist[1] = 0
   • ways[1] = 1
5. Пока очередь не пуста:
   • достать вершину v;
   • для каждого соседа to:
     • если dist[to] == -1:
       • dist[to] = dist[v] + 1
       • ways[to] = ways[v]
       • добавить to в очередь;
     • иначе если dist[to] == dist[v] + 1:
       • ways[to] += ways[v]
       • взять по модулю 1000000007.
6. После BFS:
   • если dist[n] == -1, вывести -1 0;
   • иначе вывести dist[n] и ways[n] mod 1000000007.

4. Почему это работает

Докажем корректность алгоритма.

Почему правильно находится кратчайшее расстояние

BFS в невзвешенном графе обходит вершины слоями:

• сначала стартовая вершина на расстоянии 0,
• затем все вершины на расстоянии 1,
• затем все вершины на расстоянии 2,
• и так далее.

Поэтому в момент, когда вершина to посещается впервые, значение dist[v] + 1 действительно является минимальным возможным расстоянием до неё. Значит, dist[to] вычисляется правильно.

Почему правильно считается число кратчайших путей

Рассмотрим произвольную вершину to.

Все кратчайшие пути в to должны приходить из некоторой вершины v, для которой:

• есть ребро v -> to,
• dist[v] + 1 = dist[to].

То есть последним шагом кратчайшего пути в to обязательно является переход из вершины предыдущего слоя.

Когда алгоритм рассматривает ребро v -> to:

• если to ещё не была открыта, то найден первый кратчайший способ попасть в неё, и количество путей равно ways[v];
• если to уже была открыта на том же кратчайшем расстоянии, то найден ещё один набор кратчайших путей, и мы прибавляем ways[v].

Мы не прибавляем пути из вершин, для которых dist[v] + 1 не равно dist[to], потому что такие пути не являются кратчайшими.

Значит, в ways[to] в итоге накапливается сумма количеств путей из всех вершин предыдущего слоя, из которых можно попасть в to. Это и есть точное число кратчайших путей.

Почему учитываются кратные рёбра

Если между u и v есть несколько перегонов, то в списке смежности вершина v встретится в списке соседей u несколько раз. Алгоритм обработает каждое такое ребро отдельно.

Это правильно, потому что маршруты, отличающиеся хотя бы одним перегоном, считаются разными.

5. Сложность

Пусть n — число станций, m — число перегонов.

• Построение графа: O(m)
• Обход BFS: O(n + m)

Итоговая асимптотика: O(n + m)

По памяти:

• список смежности: O(n + m)
• массивы dist, ways, очередь: O(n)

Итого по памяти: O(n + m)

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);
    vector<long long> ways(n + 1, 0);
    queue<int> q;

    dist[1] = 0;
    ways[1] = 1;
    q.push(1);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : g[v]) {
            if (dist[to] == -1) {
                dist[to] = dist[v] + 1;
                ways[to] = ways[v];
                q.push(to);
            } else if (dist[to] == dist[v] + 1) {
                ways[to] += ways[v];
                if (ways[to] >= MOD) {
                    ways[to] %= MOD;
                }
            }
        }
    }

    if (dist[n] == -1) {
        cout << -1 << " " << 0 << "\n";
    } else {
        cout << dist[n] << " " << (ways[n] % MOD) << "\n";
    }

    return 0;
}

7. Код на Python 3

MOD = 1000000007

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

dist = [-1] * (n + 1)
ways = [0] * (n + 1)

queue = [0] * n
head = 0
tail = 0

dist[1] = 0
ways[1] = 1
queue[tail] = 1
tail += 1

while head < tail:
    v = queue[head]
    head += 1

    for to in g[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            ways[to] = ways[v]
            queue[tail] = to
            tail += 1
        elif dist[to] == dist[v] + 1:
            ways[to] += ways[v]
            if ways[to] >= MOD:
                ways[to] %= MOD

if dist[n] == -1:
    print(-1, 0)
else:
    print(dist[n], ways[n] % MOD)