Link: http://pl.spoj.com/problems/AL_10_05/
Mój kod: TLE (na razie nie umieszczam, chodzi o podejście do problemu )
Problem: Szybkie znalezienie drogi pomiędzy wierzchołkami A i B o najniższej maksymalnej wysokości.
Vertices=5000
Edges=50000
Queries=10000
Sposób nr1: Mamy zapytania, więc czemu by nie wygenerować sobie tabelki szczytów pomiędzy wszystkimi wierzchołkami i z niej nie podawać odpowiedzi. Floyd-Warshall. O(V^3) TLE.
Sposób nr2: Q jest dosyć małe, więc czemu by nie odpowiadać na zapytania "w locie". Djikstra. O(VlogV+E)*Q TLE.
Sposób nr3: A można przecież wyznaczyć sobie najpierw tę tabelkę i odpowiadać w czasie stałym, gdyż Q>V. O(VlogV+E)*V TLE.
Sposób nr4: A jakby tak jeszcze zminimalizować liczbę wywołań tej Djikstry i wywoływać ją tylko dla tych wartości, które autentycznie pojawią się na wejściu. W zależności od testów, czasem zaoszczędzimy trochę czasu, a skoro graf jest nieskierowany to wystarczy wywoływać ją dla min(A,B) lub max(A,B). TLE.
Chętnie przyjmę jakieś wskazówki