Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | misiune.in, misiune.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Andrada Georgescu •andradaq | |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Misiune
Eşti un super-erou în anul 2222 şi ai primit următoarea misiune: pornind de pe planeta ta natală, Ilop, va trebui să încerci să ajungi pe Acinhet, altfel lumea va fi distrusă de o armată de monştri verzi.
Pentru a putea îndeplini acest lucru, îţi este dată harta universului: N planete şi M conexiuni interplanetare bidirecţionale ce leagă aceste planete între ele, fiecare necesitând un timp de parcurgere şi o anumită cantitate de combustibil pentru a fi parcursă.
Deoarece te deplasezi cu viteza luminii, regulile cu care eşti obişnuit nu mai funcţionează, iar timpul total se va obţine prin înmulţirea timpilor de pe parcurs.
Există unele planete cheie pe care îţi poţi alimenta nava. O planetă cheie are proprietatea că o dată cu dispariţia ei (din cauza unei catastrofe de proporţii, să zicem), s-ar pierde legatură între cel puţin două planete între care acum există drum (*un drum* este format din una sau mai multe conexiuni interplanetare).
La plecare eşti pus să îţi alegi o navă, din cele K disponibile, pentru fiecare dintre ele fiind specificată capacitatea rezervorului. Urmăreşti să poţi parcurge drumul de la Ilop la Acinhet în timp minim, dar, de asemenea, fiind vremuri de criză, şi să alegi nava cu capacitatea rezervorului minimă care îţi permite acest lucru. Nu uita că îţi poţi reumple rezervorul pe parcurs, dacă ajungi pe o planetă cheie.
Cerinţă
Va trebui să analizezi harta prezentată şi să determini timpul minim în care poţi ajunge şi nava aleasa (cea cu capacitatea minimă pentru care se obţine acest timp), precum şi drumul pe care îl vei alege. Deoarece timpul minim poate fi un număr foarte mare, nu trebuie să afli decît ultimele 6 cifre ale sale, ca să poţi verifica la destinaţie corectitudinea calculelor tale.
Date de intrare
Fişierul de intrare misiune.in:
- pe prima linie N, M şi K, separate de câte un spaţiu, cu semnificaţia din enunţ
- pe a 2-a linie numerele prin care sunt codificate planeta de start şi planeta destinaţie
- pe a 3-a linie K numere întregi capi reprezentând capacităţile navelor dintre care poţi alege
- în continuare, m linii de forma: x i y i t i c i, cu semnficaţia: de la x i la y i (şi de la y i } la {*x i) se poate ajunge în t i unităţi de timp folosind o cantitate c i de combustibil
Date de ieşire
În fişierul de ieşire misiune.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| misiune.in | misiune.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
