Fişierul intrare/ieşire:trenuri.in, trenuri.outSursăLot Cluj 2009, Baraj 5
AutorAlexandru TandrauAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test1.4 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trenuri

Ivan trebuie să ajungă la Cluj-Napoca pentru a participa la pregatirile Lotului National de Informatică. Pentru aceasta, el a ales ca mijloc de transport trenul. El dispune de la Ministerul Educatiei, Cercetării şi Inovării de o sumă pentru transport pe care nu trebuie să o depaşească. Lui Ivan nu-i place să aştepte, aşa că ar dori ca timpul maxim de aşteptare între două trenuri să fie cât mai mic.

Cerinţă

Fiind date bugetul lui Ivan şi lista tuturor trenurilor care circulă, împreună cu costul unui bilet, ora de plecare şi ora de sosire a trenului, să se găsească cel mai bun mod de a ajunge din oraşul 1 în oraşul N, conform cerinţelor lui Ivan.

Date de intrare

Pe prima linie a fişierului trenuri.in se află 3 numere întregi: N (numărul de oraşe), M (numărul de trenuri) şi B (bugetul lui Ivan). Pe următoarele M linii se găsesc descrierile trenurilor. Pe linia i + 1 se găsesc numerele întregi a, b, c, p, s (separate prin câte un singur spaţiu) cu semnificaţia că există un tren care pleacă din oraşul a la momentul de timp p, ajunge în b la momentul de timp s, şi costul unui bilet la acest tren este c.

Date de ieşire

În fişierul trenuri.out se vor scrie pe prima linie 2 numere întregi, T şi C, reprezentând timpul minim de aşteptare şi costul biletelor. În cazul mai multor soluţii cu acelaşi T se va afişa soluţia cu C minim.

Restricţii şi precizări

  • 2 ≤ N ≤ 15 000
  • 2 ≤ M ≤ 200 000
  • 0 ≤ c ≤ 10 000
  • 0 ≤ B ≤ 2 000 000 000
  • Pentru oricare tren p < s.
  • Timpul de aşteptare nu se contorizează în staţia de început. Ivan poate veni de acasă la orice oră doreşte.
  • Un tren care pleacă la momentul p poate fi luat doar dacă Ivan ajunge în staţia de plecare la un moment de timp s ≤ p. Timpul de aşteptare este p – s.
  • Există soluţie pentru toate testele, iar timpul maxim de asteptare este cel mult 200 000 unităţi.
  • Ivan vă recomandă să parsaţi fişierul de intrare. Astfel, veţi avea mai mult timp să-l ajutaţi.

Exemplu

trenuri.intrenuri.out
5 6 20
1 2 4 2 8
2 4 5 9 11
1 3 5 1 5
3 4 1 2 6
4 5 13 12 14
4 5 10 15 20
4 19

Explicaţie

Ivan ia întâi trenul din oraşul 1 spre oraşul 2. Din oraşul 2 ia trenul spre oraşul 4, aşteptând o unitate de timp. Dupa aceea, ia trenul spre oraşul 5 la timpul 15, asteptând 4 unităţi de timp. Timpul maxim de aşteptare este 4 unităţi de timp, iar costul total este 19.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content