【ICPC PacNW 2017 Div.1】Avoiding Airports / Solution

【ICPC PacNW 2017 Div.1】Avoiding Airports / Solution


David is looking to book some travel all over the world. There are $n$ countries that he can visit, and m flights that are available. The $i$-th flight goes from country $a_i$ to country $b_i$ . It departs at time $s_i$ , and lands at time $e_i$ .

David is currently in the airport in country 1, and the current time is 0, and he would like to travel to country $n$. He does not care about the total amount of time needed to travel, but he really hates waiting in the airport. If he waits $t$ time units in an airport, he gains $t^2$ units of frustration. Help him find an itinerary that minimizes the total frustration.