Omówienie zadania Droga do domu (III etap XXVIII OI)

Podzadanie 1

Na początek przyjrzymy się podzadaniu, w którym dla każdego testu \(k=n\), czyli możemy zrobić tyle przesiadek, ile jest skrzyżowań w mieście. Ponieważ na najkrótszej trasie, którą znajdziemy, wszystkie skrzyżowania muszą być różne, więc będzie ona przechodzić przez \(n-1\) dróg i zrobimy na niej co najwyżej \(n-2\) przesiadek. Tak więc jeżeli dopuszczalne jest zrobienie \(k=n\) przesiadek, to możemy się nimi nie przejmować. A to znacząco upraszcza zadanie, ponieważ możemy całkowicie zapomnieć o liniach autobusowych i każdą z nich rozbić na przejazdy pojedynczymi drogami.

Zadanie jest grafowe i w naszym pierwszym rozwiązaniu stworzymy sobie graf, którego wierzchołki będą odpowiadać skrzyżowaniom, a krawędzie możliwym przejazdom drogami. Rozważmy pojedynczą linię autobusową, na której autobusy jeżdżą przez kolejne wierzchołki \(v_1, v_2, \ldots, v_\ell\). Oznaczmy przez \(c_{a,b}\) sumaryczny czas, jaki autobus tej linii potrzebuje na przejechanie z wierzchołka \(v_a\) do wierzchołka \(v_b\): \[c_{a,b} = \sum_{a\leq i < b} c(v_i,v_{i+1}).\]

Autobusy tej linii startują z wierzchołka \(v_1\) w momentach \(x + j \cdot y\) dla \(y\in \mathbb{N}\). Zatem w wierzchołku \(v_2\) znajdą się w momentach \(x + c_{1,2} + j \cdot y\), i tak dalej, aż w wierzchołku \(v_\ell\) znajdą się w momentach \(x + c_{1,\ell} + j \cdot y\). Zatem dla tej linii autobusowej stworzymy w grafie \(\ell - 1\) skierowanych krawędzi: dla \(1\leq i < \ell\) krawędź będzie prowadziła z wierzchołka \(v_i\) do wierzchołka \(v_{i + 1}\) oraz będzie zawierała informacje o momencie pojawienia się pierwszego autobusu tej linii w wierzchołku \(v_i\) (czyli o momencie \(x + c_{1,i}\)), o częstotliwości kursowania autobusu tą krawędzią (czyli \(y\)) oraz o czasie przejazdu tą krawędzią (czyli \(c_{i,i + 1})\).

Wobec tego nasz graf będzie zawierał \(V=n\) wierzchołków i \(E\leq L\) krawędzi, gdzie \(L = \sum_{1\leq i\leq s} \ell_i\). W takim grafie będziemy chcieli znaleźć najkrótszą ścieżkę z wierzchołka \(1\) do \(n\), przy czym koszt przejazdu daną krawędzią nie jest stały, a zależny od czasu, w którym znajdziemy się w początkowym wierzchołku tej krawędzi. W rozwiązaniu skorzystamy z lekko zmodyfikowanego algorytmu Dijkstry.

Oczywiście początkowo najkrótsze odległości w każdego wierzchołku inicjujemy na \(d[v]=\infty\), oprócz wierzchołka początkowego, w którym dajemy \(d[1]=t\) (czyli chwilę, w której Bajtek wychodzi ze szkoły). Załóżmy, że doszliśmy do wierzchołka \(v\) w czasie \(d[v]\) i relaksujemy krawędź \(v\to w\) o parametrach \(x, y, c\). Musimy teraz popatrzeć, kiedy będzie najwcześniejsza możliwość przejścia tą krawędzią, to znaczy, kiedy w wierzchołku \(v\) pojawi się najwcześniejszy autobus po czasie \(d[v]\), czyli musimy znaleźć najmniejsze \(j\in\mathbb{N}\), że \(x + j \cdot y \geq d[v]\).

Dla takiego \(j\), odległość w wierzchołku \(d[w]\), będziemy mogli zrelaksować wartością \(x + j \cdot y + c\), czyli zapisać, że \(d[w] := \min(d[w],\ x+j\cdot y + c)\). Wartość \(j\) możemy obliczyć za pomocą wyszukiwania binarnego albo w czasie stałym za pomocą wzoru: \[j = \left\{\begin{array}{ll} 0 & \textrm{dla}\ x \geq d[v], \\ \lceil (d[v]-x) / y \rceil & \textrm{dla}\ x < d[v]. \end{array}\right.\]

Ponieważ złożoność algorytmu Dijkstry dla grafu o \(V\) wierzchołkach i \(E\) krawędziach to \(O((V + E)\log V)\), więc w naszym przypadku dostaniemy \(O((n + L) \log n)\).

Podzadanie 3

Podczas podróży nie będzie nas jedynie interesowało, na jakim skrzyżowaniu się znajdujemy, ale również, ile jeszcze przesiadek możemy wykorzystać. Standardowy pomysł jest więc taki, żeby wierzchołki naszego grafu reprezentowały zarówno położenie na skrzyżowaniu, jak i informacje o wykorzystanych przesiadkach. Przy czym zamiast o przesiadkach wygodniej nam będzie myśleć o \(k + 1\) biletach, które mamy do dyspozycji. Wtedy wierzchołek \((v,b)\) w grafie będzie zawierał numer skrzyżowania \(v\) oraz liczbę biletów \(b\), które już zużyliśmy. Tak więc liczba wierzchołków w naszym grafie będzie \(V=O(nk)\).

Ponieważ każdorazowe wejście do autobusu będzie zużywało nam jeden bilet, będziemy musieli również kontrolować, w których momentach wchodzimy i wychodzimy z autobusu. Najprościej będzie to zrobić, jeżeli całą podróż jednym autobusem będziemy reprezentować za pomocą jednej krawędzi. Tak więc jeżeli \(i\) oraz \(j\) są dowolnymi skrzyżowaniami na pewnej linii (niekoniecznie kolejnymi, ale \(i<j\)), to dla każdego ich wyboru w grafie tworzymy krawędź skierowaną z wierzchołka \((v_i,b)\) do wierzchołka \((v_j,b+1)\). Pierwszy autobus pojawi się w wierzchołku \((v_i,b)\) o czasie \(x + c_{1,i}\), każdy kolejny \(y\) minut po poprzednim, a koszt przejazdu krawędzią to \(c_{i,j}\).

W takim grafie szukamy najkrótszej ścieżki ze stanu \((1,0)\) do dowolnego stanu \((n,b)\) dla \(b\leq k+1\). Liczba krawędzi, które stworzymy, jest \(E=O(L^2 k)\), bo dla każdej linii robimy przejazd pomiędzy każdą parą skrzyżowań na tej linii, a dodatkowo każdą krawędź powtarzamy dla wszystkich liczb biletów.

Zatem, jeżeli do rozwiązania użyjemy algorytmu Dijkstry, to dostaniemy całkiem dużą złożoność \(O((n + L^2) k \log(nk))\).

Okazuje się, że możemy dość łatwo pozbyć się logarytmu z tej złożoności. Jest tak dlatego, że wprowadzenie liczby biletów do stanów spowodowało, że nasz skierowany graf jest acykliczny, ponieważ przejście każdą krawędzią zwiększa nam liczbę zużytych biletów w stanie.

Tak więc do znalezienia najkrótszej ścieżki możemy zastosować proste programowanie dynamiczne na DAG-u. Jego złożoność czasowa będzie liniowa ze względu na rozmiar grafu, czyli \(O((n+L^2)k)\).

Pełne rozwiązanie

Będziemy chcieli uniknąć kwadratowej liczby krawędzi, a zamiast tego jakoś efektywnie pamiętać, że kontynuujemy jazdę autobusem. Pomysł jest taki, że będziemy mieli dwa osobne rodzaje stanów na opis sytuacji, w którym jesteśmy na pewnym skrzyżowaniu i czekamy na przystanku na autobus, oraz przez pewne skrzyżowanie przejeżdżamy, siedząc w autobusie. Zatem stan \((v,a,b)\) w grafie opiszemy trzema liczbami: \(v\) oznaczać będzie skrzyżowanie, w którym się znajdziemy, \(a\) będzie kodować, że albo jesteśmy na przystanku, albo w autobusie pewnej linii, zaś \(b\) będzie oznaczać liczbę zużytych biletów.

Zakładamy, że wartość \(a = 0\) oznacza stan, w którym czekamy na przystanku, natomiast \(1\leq a \leq s\) oznacza numer linii autobusowej, którą jedziemy. W celu oszacowania liczby wierzchołków w tym grafie zauważamy, że dla każdego \(a=0\) mamy tyle wierzchołków, ile skrzyżowań w grafie, czyli \(n\). Natomiast sumaryczna liczba wierzchołków dla dodatnich \(a\) jest równa \(L\). Oczywiście musimy uwzględnić jeszcze wartości \(b\), zatem całość musimy jeszcze pomnożyć razy \(k\), więc \(V=O((n+L)k)\).

W grafie będziemy mieli trzy rodzaje krawędzi: odpowiedzialne za wsiadanie do autobusu, przejazd drogą oraz wysiadanie z autobusu.

Wsiadanie do autobusu linii \(a\) na skrzyżowaniu \(v_i\) opisuje krawędź \((v_i,0,b) \to (v_i,a,b+1)\), ponieważ taka operacja zużywa nam jeden bilet. Koszt krawędzi będzie oznaczał czas oczekiwania na najbliższy autobus i będzie zależał od wartości \(x + c_{1,i}\) oraz \(y\).

Drugi rodzaj krawędzi oznacza przejazd drogą autobusem linii \(a\) ze skrzyżowania \(v_i\) do skrzyżowania \(v_{i+1}\), zatem jest to krawędź \((v_i,a,b) \to (v_{i+1},a,b)\). Taki przejazd nie zmienia liczby biletów, a jego koszt jest równy dokładnie \(c_{i,i+1}\).

W końcu mamy krawędź oznaczającą wyjście z autobusu linii \(a\) na skrzyżowaniu \(v_i\), czyli krawędź \((v_i,a,b) \to (v_i,0,b)\). Koszt przejścia tą krawędzią będzie zerowy.

Zauważmy, że dla każdego wierzchołka grafu opisanego przez trójkę \((v,a,b)\) dla \(a>0\) mamy co najwyżej jedną krawędź wchodzącą do tego wierzchołka (oznaczającą wejście do autobusu) i co najwyżej dwie krawędzie wychodzące z tego wierzchołka (oznaczające jazdę autobusem i wyjście z autobusu). To pokazuje, że liczba krawędzi w tym grafie jest rzędu \(E=O(L k)\).

W grafie tym oczywiście szukamy najkrótszej ścieżki z wierzchołka \((1,0,0)\) do wierzchołka \((n,0,b)\), gdzie \(b\leq k+1\). Znowu możemy tu albo użyć algorytmu Dijkstry, albo zauważyć, że nasz graf nadal jest acykliczny, choć teraz jest to troszkę mniej oczywiste. Ale wystarczy popatrzeć, że wierzchołki dla ustalonego \(a>0\) oraz \(b\) tworzą jedną ścieżkę, a dodatkowo prowadzą do nich krawędzie z wierzchołków dla \(a = 0\) i \(b-1\), a wychodzą z nich krawędzie do wierzchołków dla \(a = 0\) i \(b\). Wobec tego łatwo jest uporządkować te wierzchołki topologicznie.

Ostatecznie złożoność czasowa takiego rozwiązania szukania najkrótszej ścieżki na DAG-u to będzie \(O((n+L) k)\).