Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | Invalid task id .in, Invalid task id .out | Sursă | Invalid task id |
| Autor | Invalid task id | Adăugată de | Invalid task id |
| Timp execuţie pe test | Invalid task id sec | Limită de memorie | Invalid task id kbytes |
| Scorul tău | Invalid task id | Dificultate | Invalid task id |
Vezi solutiile trimise | Statistici
Invalid task id
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
Coach
Sunteti antrenorul ciclistului Adirem Onamihs care, in ciuda numelui ciudat, este foarte talentat. In curant va avea loc un eveniment sportiv, un prilej foarte bun de a-l antrena pe ciclist. Pentru organizarea evenimentului s-au amenajat N intersectii si M drumuri bidirectionale intre aceste intersectii. Pentru fiecare drum se cunosc numarul de minute necesare pentru parcurgerea lui. La fiecare intersectie ciclistul care trece pe acolo este obligat sa serveasca o bautura energizanta si racoritoare. Bautura difera de la intersectie la intersectie si se cunosc deja numarul de calorii ale fiecarei bauturi.
Ca un mare antrenor, aveti un plan special pentru Adirem. Doriti ca durata traseului pe care il alege Adirem sa aiba exact T ore, insa nu vreti sa-i planuiti intregul traseu (Adirem trebuie sa isi antreneze si mintea, nu numai corpul). Ii veti preciza lui Adirem doar intersectia de unde isi incepe traseul si intersectia unde il termina. Adirem invata repede - el stie intotdeauna sa aleaga traseul optim (drumul cel mai scurt dintre cele doua intersectii). Atunci cum il puteti face sa mearga exact T ore? Dupa cateva portii de creatina, va vine ideea salvatoare: ii veti interzice trecerea prin anumite intersectii, sub pretextul ca valoarea calorica a bauturii servite in intersectia respectiva nu este benefica pentru antrenamentul lui. Astfel, ii veti preciza o limita inferioara si una superioara pentru numarul de calorii ale bauturilor pe care el are voie sa le bea. Adirem nu va trece decat prin intersectiile unde se serveste o bautura cu valoare calorica intre limitele date.
Cum numarul de intersectii este destul de mare, va trebui sa scrieti un program care sa calculeze cele patru variabile in antrenamentul lui Adirem: intersectia de start, intersectia de finish, valoarea calorica minima pe care poate sa o consume si valoarea calorica maxima, astfel incat drumul cel mai scurt dintre cele doua intersectii (care sa respecte restrictiile) sa dureze T minute.
Date de Intrare
Prima linie a fisierului coach.in contine trei numere intregi N, M si T reprezentand numarul de intersectii, drumuri, respectiv timpul dorit. Urmatoarele N linii contin cate un numar - valoarile calorice a bauturilor din intersectii, in ordine (de la 1 la N). Urmatoarele M linii contin cate un triplet de numere: doua intersectii si durata drumului dintre ele.
Date de Iesire
Fiserul coach.out va contine o linie, pe care se vor afla cele patru valori gasite: nodul de start, nodul de finish, valoarea calorica minima si valoarea calorica maxima. Nodurile vor fi intregi intre 1 si N, iar valorile calorice vor fi intregi intre 1 si 10.000 (inclusiv).
Restrictii si precizari
o 1 <= N <= 100, 1 <= M <= 4.950, 1 <= T <= 1.000.000
o Costurile muchiilor - intregi intre 1 si 10.000 (inclusiv)
o Caloriile bauturilor - intregi intre 1 si 10.000 (inclusiv)
o Intersectiile gasite (de start si de finish) trebuie sa respecte si ele restrictiile calorice
o O bautura cu valoarea calorica x poate fi bauta daca si numai daca cmin <= x <= cmax, unde cmin si cmax sunt valorile calorice minime si maxime gasite
o Intre doua intersectii exista maxim un drum
o Valorile calorice sunt distincte
o Exista intotdeauna solutie
Exemplu
coach.in coach.out
6 9 11 3 6 20 55
40
10
20
30
60
50
1 2 2
1 3 2
1 4 4
1 6 10
2 3 3
2 4 1
4 5 1
4 6 5
5 6 2
