Аэропорты открываются
Авиасеть строят постепенно: аэропорты открываются по одному, а рейсы между ними расписаны заранее. Рейс можно выполнить, только когда открыты оба его конца, а пересаживаться можно лишь в открытых аэропортах. Аналитик хочет следить, как растёт сеть: после открытия каждого аэропорта — сколько упорядоченных пар открытых аэропортов (a, b), a ≠ b, уже связаны маршрутом и какова сумма длин кратчайших маршрутов по всем таким парам.
Рейсы односторонние: рейс из a в b не означает рейса обратно. Между одной парой аэропортов рейсов может быть несколько — разной длины. Два теста — настоящие рейсы между 21 аэропортом из статьи, с длинами в километрах по дуге большого круга.
Вход
В первой строке n и m (1 ≤ n ≤ 150, 0 ≤ m ≤ 25 000) — число аэропортов и рейсов. Дальше m строк a b w: рейс из a в b длиной w (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ w ≤ 10⁶). В последней строке — n различных номеров аэропортов в порядке открытия.
Выход
n строк: после открытия очередного аэропорта — два числа через пробел, число связанных пар и сумму длин их кратчайших маршрутов.
Примеры
Пример 1
4 4 1 2 5 2 3 4 3 1 2 3 4 7 2 1 4 3
0 0 1 5 1 5 9 67
Пример 2
5 5 1 2 10 1 2 3 2 1 3 4 5 1 5 3 6 3 5 4 1 2
0 0 1 6 3 14 3 14 5 20
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Можно после каждого открытия запускать Флойда — Уоршелла по открытым аэропортам заново. Это верно, но сколько это стоит при 150 аэропортах?
2Подсказка 2
Что знает таблица Флойда — Уоршелла после шага с вершиной k? И обязательно ли перебирать k в порядке номеров?
3Идея
После того как пройдены вершины k1, …, kt, клетка d[i][j] равна длине кратчайшего маршрута из i в j с пересадками только в этих вершинах — для любых i и j, открытых или нет. Порядок вершин доказательство не использует. Возьмём его равным порядку открытия: тогда после t-го шага пересадки разрешены ровно в открытых аэропортах, и остаётся сложить клетки между открытыми аэропортами. Один проход Флойда — Уоршелла вместо n проходов.
4Разбор
Таблица d — прямые рейсы, из нескольких рейсов между парой берём самый короткий. Затем для каждого аэропорта k в порядке открытия делаем обычный шаг алгоритма по всем строкам и столбцам: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Строки закрытых аэропортов тоже нужно обновлять: когда аэропорт i откроется, его строка уже должна знать маршруты через всё открытое раньше, а пересчитывать её задним числом будет некогда. После шага складываем конечные d[i][j] по парам открытых i ≠ j.
Почему в таблице нет маршрутов через закрытые аэропорты: закрытые аэропорты ещё не были вершиной k, а по инварианту промежуточные вершины всех записанных маршрутов — только пройденные k. Концы маршрута — i и j — открыты, потому что мы суммируем только по ним.
Эта задача — вариант известной задачи, где вершины, наоборот, удаляют по одной и ответ нужен перед каждым удалением. Её решают так же, прочитав порядок удалений с конца: последняя удалённая вершина — первая открытая.
Сумма бывает большой: до 150 · 149 пар по маршруту до 149 · 10⁶ — около 3 · 10¹² — в Go нужен int64.
4+Решение
5Сложность
O(n³) на шаги алгоритма и O(n³) в сумме на подсчёт сумм (на шаге t — t² клеток), память O(n²). Пересчёт с нуля после каждого открытия — O(n⁴): при n = 150 это около 1,3 · 10⁸ шагов, для Python слишком много.
6Типичные ошибки
- Пересчёт с нуля. Верно, но в десятки раз дольше — пятый тест.
- Обновлять только открытые строки. Строка аэропорта, который откроется позже, пропустит шаги через ранее открытые аэропорты, и маршруты из него окажутся длиннее или пропадут.
- Пары с закрытыми концами. Таблица знает маршрут из открытого аэропорта в закрытый, но такой пары ещё нет.
- Несколько рейсов между парой. Брать последний прочитанный, а не самый короткий.
- Переполнение. Сумма не помещается в 32 бита.