Максим Щерба
Нехай — множина всіх простих шляхів із міста 1 до міста , — деякий такий шлях, k_p — сума c_i по всіх ребрах шляху , b_p — сума d_i по всіх ребрах шляху . Тоді f(t)=\min\limits_{p \in P}\{k_p t + b_p\} — опукла вгору кусково-лінійна функція.
Згенеруємо всі шляхи з множини . Кожен із них задає пряму f_p(t)=k_p t + b_p. Побудуємо опуклу оболонку цих прямих, таким чином знайдемо функцію у явному вигляді. З огляду на адитивність інтеграла інтеграл на проміжку дорівнює сумі інтегралів на проміжках, де функція — лінійна. Інтеграл від лінійної функції можна обчислити, використовуючи табличні інтеграли: \int_l^r (kt + b)dt = k \frac{r^2-l^2}{2}+b(r-l).
Складність розв'язку: .