Задача №114971. Доставка еды
Столица Берляндии — огромный город, в котором есть \(n\) перекрёстков, пронумерованных целыми числами от \(1\) до \(n\).
Движение по городу организованно особым образом. Всего в городе есть \(m\) односторонних дорог, \(i\)-я из которых выходит из перекрёстка \(a_i\) и входит в перекрёсток \(b_i\). У некоторых дорог есть их продолжения. При въезде на перекрёсток по дороге с номером \(i\) и выезде по дороге \(j\), если \(j\)-я дорога является продолжением \(i\)-й, то время проезда по дороге \(j\) будет на секунду меньше времени проезда по дороге \(i\) (но если по дороге \(i\) время движения было равно \(0\), то по дороге \(j\) время движения тоже будет равно \(0\)). Если же дорога \(j\) не является продолжением \(i\)-й, то машине придётся сбросить скорость для поворота и время проезда по дороге \(j\) будет равно \(c_j\).
Более формально, для каждой дороги зафиксировано число \(d_i\), обозначающее продолжение дороги. Если \(d_i\) равно \(-1\), то у \(i\)-й дороги нет продолжения, а если \(d_i > 0\), то продолжением дороги \(i\) является дорога c номером \(d_i\).
Для каждой дороги зафиксировано время первоначального проезда по ней, равное \(c_i\). При движении по некоторому пути время проезда по дороге с номером \(i\) определяется следующим образом:
- Если дорога \(i\) является первой на пути или не является продолжением предыдущей на пути, то время проезда по ней равно \(c_i\).
- Если дорога \(i\) является продолжением предыдущей на пути и по предыдущей дороге машина двигалась \(x\) секунд, то время движения по текущей дороге равно \(max(0, x - 1)\) секунде.
Недавно вы открыли новый ресторан на перекрёстке с номером \(1\) и хотите начать доставлять еду в разные точки города. Для каждого перекрёстка вы хотите узнать, за какое минимальное время можно доставить еду на этот перекрёсток, начиная движение с перекрёстка номер 1.
В первой строке даны три целых числа \(n\), \(m\) и \(g\) (\(1 \le n, m \le 500\,000\), \(0 \le g \le 10\)) — число перекрёстков в городе, число дорог в городе и номер группы тестов.
В следующих \(m\) строках даны по четыре целых числа \(a_i\), \(b_i\), \(c_i\) и \(d_i\) (\(1 \le a_i, b_i \le n\), \(1 \le c_i \le 10^9\), \(d_i = -1\) или \(1 \le d_i \le m\)) — начало \(i\)-й дороги, конец \(i\)-й дороги, время первоначального проезда по \(i\)-й дороге и номер продолжения \(i\)-й дороги (\(d_i = -1\) если у \(i\)-й дороги нет продолжения).
Гарантируется, что если у дороги есть продолжение, то оно выходит из перекрёстка \(b_i\). Также гарантируется, что если \(d_i \neq -1\), то \(c_{d_i} \ge c_i - 1\). Обратите внимание, что между одной и той же парой перекрёстков может проходить несколько дорог, одна дорога может быть продолжением нескольких дорог, а так же у разных дорог, входящих в перекрёсток, могут быть разные продолжения.
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно минимальному времени, за которое можно доставить еду до перекрёстка номер \(i\). Если доставить еду до перекрёстка номер \(i\) нельзя, выведите \(-1\).
В первом примере до перекрёстка 2 можно доехать по дороге 1 за 5 секунд. Чтобы доехать до перекрёстка 3, надо сначала проехать по дороге 1, а затем по её продолжению дороге 2. За счёт того, что дорога 2 является продолжением дороги 1, время движения по ней составит 4 секунды, поэтому до перекрёстка 3 можно доехать за 9 секунд.
Во втором примере можно добраться до перекрёстка 2 за 5 секунд по дороге 1. До перекрёстка 3 можно добраться за 8 секунд по дороге 3. До перекрёстка 4 можно добраться за 12 секунд по дорогам с номерами 1, 4, 2. Время движения по ним составит \(5 + 4 + 3 = 12\) секунд. До перекрёстка 5 доехать никак нельзя, так как в него не входит ни одна дорога.
В третьем примере оптимальный путь до перекрёстка 4 пройдёт по дорогам 1, 2, 3, время движения будет равно \(10 + 4 + 3 = 17\).
Тесты к этой задаче состоят из 10 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(c_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 10 | \(n \le 1000\) | \(m \le 1000\) | – | 0 | |
| 2 | 8 | \(n \le 10\,000\) | \(m \le 10\,000\) | – | 0, 1 | |
| 3 | 9 | – | – | – | – | У всех дорог \(d_i = -1\) |
| 4 | 9 | – | – | \(c_i = 1\) | – | |
| 5 | 11 | \(n \le 100\,000\) | \(m \le 100\,000\) | \(c_i \le 10\) | 0 | |
| 6 | 16 | – | – | – | 3 | Каждая дорога является продолжением не более одной другой |
| 7 | 19 | \(n \le 100\,000\) | \(m \le 100\,000\) | – | 0 – 2, 5 | |
| 8 | 6 | \(n \le 250\,000\) | \(m \le 250\,000\) | – | 0 – 2, 5, 7 | |
| 9 | 6 | \(n \le 400\,000\) | \(m \le 400\,000\) | – | 0 – 2, 5, 7, 8 | Offline-проверка |
| 10 | 6 | – | – | – | 0 – 10 | Offline-проверка |
3 2 0 1 2 5 2 2 3 10 -1
0 5 9
5 4 0 1 2 5 4 3 4 10 -1 1 3 8 2 2 3 7 2
0 5 8 12 -1
4 4 0 1 2 10 3 2 2 4 3 2 4 9 4 4 1 10 1
0 10 -1 17
4 5 0 1 2 10 -1 1 3 1 3 3 4 7 4 4 2 6 5 2 2 5 5
0 1 1 1