Один бесплатный проезд
Между n городами проложены m платных дорог, по каждой можно ехать в обе стороны, и у каждой своя цена проезда. У вас есть один купон: он делает бесплатной одну любую дорогу на вашем пути. Сколько придётся заплатить, чтобы добраться из города 1 в город n, если тратить купон с умом?
Вход
В первой строке n и m (2 ≤ n ≤ 50 000, 1 ≤ m ≤ 100 000). Дальше m строк a b c — дорога между городами a и b стоимостью c тенге (1 ≤ c ≤ 10⁶).
Выход
Наименьшую сумму, которую придётся заплатить, или -1, если из 1 в n не доехать. Купон можно и не использовать, но выгоднее использовать всегда, если ехать хоть по одной дороге.
Примеры
Пример 1
4 4 1 2 3 2 3 50 3 4 2 1 4 60
0
Пример 2
4 4 1 2 10 2 4 10 1 3 1 3 4 100
1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Самое очевидное решение: найти самый дешёвый путь и сделать бесплатной самую дорогую дорогу на нём. Проверьте его на втором примере.
2Подсказка 2
Чтобы знать, сколько ещё можно сэкономить, мало знать, в каком городе вы стоите. Что ещё нужно помнить о пройденном пути?
3Идея
Состояние путешественника — это пара «город, потрачен ли купон». Построим граф на таких парах: из (u, 0) по дороге (u, v, c) можно попасть в (v, 0) за c или в (v, 1) бесплатно, а из (u, 1) — только в (v, 1) за c. Это два этажа одного графа, и купон — лестница со второго на первый. Ответ — кратчайший путь из (1, 0) в любое из (n, 0), (n, 1). Его находит обычная Дейкстра: все веса неотрицательны.
4Разбор
Граф на парах не нужно строить явно: соседей пары легко перечислить на лету. Храним dist[v][used], в куче — тройки (расстояние, город, флаг). При обработке (u, used) для каждой дороги пробуем два перехода: заплатить и, если купон ещё цел, проехать бесплатно.
Почему жадная идея из первой подсказки неверна: во втором примере самый дешёвый путь 1 → 2 → 4 стоит 20, и купон снимает 10. А путь 1 → 3 → 4 стоит 101, но купон снимает с него 100, и остаётся 1. Купон меняет то, какой путь кратчайший, поэтому решать эти задачи по очереди нельзя.
Тот же приём работает для k купонов (k + 1 этаж), для «не больше k пересадок», для «бензина хватает на L километров» — всё, где к вершине нужно приписать немного памяти о пройденном.
4+Решение
5Сложность
Состояний 2n, переходов не больше 3 на каждое направление дороги: O((n + m) log n). Для k купонов — в k + 1 раз больше.
6Типичные ошибки
- Скидка на самую дорогую дорогу кратчайшего пути. Не проходит второй пример — см. разбор.
- Переполнение. Сумма доходит до 5·10¹⁰: в Go тип
int64-битный и справляется, а в языках с 32-битнымintответ на восьмом тесте испортится. - Одно расстояние на город вместо двух. Тогда путь «дёшево, но купон уже потрачен» затирает путь «чуть дороже, но купон цел», хотя второй потом может сэкономить гораздо больше. Состояния с разным флагом должны жить отдельно.