Wyszukiwanie maksimum lokalnego cz II. - O szybkim turyście i chciwym bacy

Treść tego zadania jest bardzo głupia :) Chciałem ją zmodyfikować, ale stwierdziłem, że tak będzie śmieszniej :) Miłej lektury.

Mamy dany graf w którym wyróżniono dwa wierzchołki - A oraz B. Z każdą krawędzią i są związane dwie liczby rzeczywiste: a_i oraz b_i. Koszt przejechania tej krawędzi w czasie t wynosi a_it + b_i.
Turysta chce przejść z punktu A do B. Turysta jest bardzo sprytny i w dowolnym czasie t potrafi znaleźć najtańszą drogę z punktu A do B. Jest też bardzo bardzo szybki (struś pędziwiatr to przy nim żółw) i całą trasę potrafi przebiec w czasie zerowym!

Pytanie: W jakim czasie T z przedziału [0, 1] baca powinien wypuścić turystę ze swojej chatki, aby zmaksymalizować swój zysk?

Co ma z tym wspólnego maksimum lokalne? Dla każdej ścieżki w grafie jej koszt jest funkcją liniową zależną od T.
Zatem baca jeśli wypuści turystę w czasie T zarobi min(T) dudków, gdzie min(T) jest dane wzorem:
Spójrzmy na wykres tej funkcji.
Funkcja ma tylko jedno maksimum lokalne. Możemy zatem użyć wyszukiwania ternarnego (wystarczy tylko uogólnić algorytm na przedział rzeczywisty - co pozostawiam jako proste ćwiczenie ;) )