h1(#MaxSubSum). 'B. Avioane2':problema/Avioane2

Din zborurile care sunt date, se construieste un graf in care nodurile sunt perechi de forma <tex>(aeroport, timp)</tex>. Sunt suficiente numai perechile din zborurile initiale (cel mult <tex>2*M</tex> perechi, deci tot atatea noduri), plus inca o pereche <tex>(1, 0)</tex> (aeroportul 1, timpul 0) de la care se porneste.
 
Muchiile se leaga in felul urmator:
1. intre nodurile de forma <tex>(aeroport_d_e_c, timp_d_e_c)</tex> si <tex>(aeroport_a_t_e_r, timp_a_t_e_r)</tex> (intre care exista zbor) se leaga o muchie avand costul <tex>P</tex> corespunzator zborului. Se obtin <tex>M</tex> muchii de zbor;
2. intre nodurile corespunzatoare aceluiasi aeroport se leaga muchii cu cost <tex>0</tex> (costul de asteptare) de la nodul cu timp mai mic la nodul imediat urmator ca timp. De exemplu, daca pentru aeroportul <tex>5</tex> am zboruri (care ajung sau pleaca) la timpii <tex>1</tex>, <tex>10</tex>, <tex>15</tex>, <tex>21</tex>, se vor pune muchii intre perechile: <tex>(5, 1) - (5, 10)</tex>, <tex>(5, 10) - (5, 15)</tex>, <tex>(5, 15) - (5, 21)</tex>. Daca cei doi ajung in aeroportul 5 la timpul 10 si vor sa plece la timpul 21, drumul <tex>(5, 10) - (5, 15) - (5, 21)</tex> va corespunde asteptarii si va avea cost 0. Se obtin cel mult <tex>2*M</tex> muchii de asteptare.
 
In continuare, se utilizeaza un algoritm de drum de cost minim ("Dijkstra":problema/dijkstra sau "Bellman-Ford":problema/bellmanford) de la nodul de plecare <tex>(1, 0)</tex> la toate celelalte noduri pentru a putea afla costul minim de a ajunge la un anumit aeroport la un anumit moment de timp.
 
Acum pentru fiecare query de forma <tex>(A, T)</tex> (aeroport, timp) se afiseaza minimul dintre distantele pana la toate nodurile <tex>(A, t)</tex>, unde <tex>t <= T</tex> sau <tex>-1</tex> daca nu exista astfel de noduri sau nu pot fi atinse. Pentru asta exista mai multe variante, de exemplu cu sortarea query-urilor si rezolvarea lor offline sau aplicand cautare binara.

?

h1(#Minlcm). 'C. Minlcm':problema/Minlcm