CS
Задачник Базовый курс EN

Задача

Электромобиль в горах

кратчайший путь взвешенный граф карты и навигация наука и физика

Электромобиль ездит по городу на холмах. У каждого перекрёстка известна высота, у каждой улицы — длина, и по улице можно ехать в обе стороны. Метр дороги стоит F единиц энергии. Подъём на единицу высоты стоит ещё U, а спуск на единицу высоты возвращает D — на спуске мотор заряжает батарею. Так проезд по улице длины ℓ с перепадом Δ стоит Fℓ + UΔ вверх и Fℓ − DΔ вниз, и второе число бывает отрицательным. Спуск никогда не возвращает больше, чем стоит такой же подъём: D ≤ U.

Машина стоит на перекрёстке s. Для каждого перекрёстка из списка найдите, сколько энергии нужно, чтобы доехать до него самым экономным маршрутом. Ответ бывает отрицательным: значит, батарея по дороге зарядится.

Один из тестов — улицы Алматы с высотами перекрёстков по съёмке SRTM и электромобиль из статьи, в милливатт-часах и дециметрах.

Вход

В первой строке — число перекрёстков n и улиц m (1 ≤ n ≤ 105, 0 ≤ m ≤ 2·105). Во второй — F, U, D (0 ≤ F ≤ 104, 0 ≤ D ≤ U ≤ 104). В третьей — высоты перекрёстков h1, …, hn, целые от 0 до 105. Дальше m строк по три числа a b ℓ — улица между перекрёстками a и b длины ℓ (1 ≤ ℓ ≤ 104, a ≠ b). Затем строка s q и строка из q номеров перекрёстков (1 ≤ q ≤ 105).

Выход

q строк: наименьшая энергия до каждого перекрёстка из списка — целое число, возможно отрицательное, — или «-», если до него не доехать.

Примеры

Пример 1

Вход
3 2
150 545 294
10 50 90
1 2 100
2 3 100
3 3
1 2 3
Выход
6480
3240
0

Пример 2

Вход
4 4
10 100 90
0 0 100 0
1 2 1000
1 3 5
3 4 5
4 2 5
1 3
2 3 4
Выход
1150
10050
1100

Ограничения

Время · Python
8000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
10 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Дейкстра не годится: веса бывают отрицательными, и во втором примере он раньше времени объявит окончательной длинную ровную дорогу. Беллман — Форд справится, но на длинной дороге из десятков тысяч перекрёстков ему нужно столько же раундов. Можно ли сделать веса неотрицательными, не меняя ответа?

2Подсказка 2

Если к весу каждой улицы u → v прибавить p(u) − p(v), вес любого маршрута из s в t изменится на одно и то же p(s) − p(t). Какое p подсказывает сама задача?

3Идея

Потенциал — высота: p(v) = D · hv. Тогда приведённый вес подъёма на Δ — Fℓ + UΔ − DΔ = Fℓ + (U − D)Δ, а спуска — Fℓ − DΔ + DΔ = Fℓ. Оба неотрицательны, потому что D ≤ U, — это утверждение «высота — потенциал» из статьи. Дейкстра на приведённых весах находит те же маршруты, а настоящая энергия получается обратным пересчётом: найденное число плюс D·(ht − hs).

4Разбор

Один Дейкстра от s с двоичной кучей. Во втором примере ровная дорога 1 → 2 длиной 1000 стоит 10 000, а объезд через холм высотой 100 — 50 + 100·100 на подъём, 50 − 90·100 на спуск и 50 по ровному — всего 1150. В приведённых весах подъём стоит 50 + 10·100 = 1050, спуск и ровная дорога — по 50, и Дейкстра честно находит объезд.

Энергия на маршруте доходит до 1014: в Go нужен int64.

4+Решение
5Сложность

O((n + m) log n) — один Дейкстра. Беллман — Форд стоит O(n·m), и на десятом тесте — дороге из сорока тысяч перекрёстков, улицы которой перечислены от дальнего конца, — ему нужно сорок тысяч раундов.

6Типичные ошибки
  • Дейкстра на настоящих весах. Перекрёсток объявляется окончательным при первом извлечении из кучи, и спуск, найденный позже, его уже не улучшит — второй пример.
  • Знак при обратном пересчёте. Приведённый вес маршрута — энергия плюс D·hs минус D·ht; чтобы вернуться к энергии, нужно вычесть D·hs и прибавить D·ht. Первый пример — спуск с холма — сразу покажет ошибку в знаке.
  • Множитель высоты вне промежутка. Годится любое c от D до U: при c = U, например, подъём стоит Fℓ, а спуск Fℓ + (U − D)Δ. Если взять c меньше D, отрицательными останутся крутые спуски, а если больше U — станут отрицательными крутые подъёмы.
  • Недостижимые перекрёстки. Город бывает из нескольких кусков — восьмой тест.

Алгоритмы задачи

GRA Алгоритм Алгоритм Джонсона Кратчайшие пути при отрицательных весах: потенциалы Беллмана — Форда, перевзвешивание и Дейкстра от каждой вершины. O(V·E + V·(V + E) log V) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи
Каталог алгоритмов