Fișierul intrare/ieșire | dragoni2.in, dragoni2.out | Sursă | OJI 2015 clasele 11-12 |
---|---|---|---|
Autor | Vlad-Alexandru Gavrilă | Adăugată de | Radu Muntean • heracle |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 32768 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Dragoni2 (clasele 11-12)
Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:
Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j între 1 și M, ruta j unește insulele Aj și Bj și are lungime Dj.
Pe fiecare insulă i (1 ≤ i ≤ N) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmaxi. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j (1 ≤ j ≤ M) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.
Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insulă i (1 ≤ i ≤ N) având cu el un dragon din specia t, el poate:
- Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i și x, bineînțeles doar dacă Dj ≤ Dmaxt.
- Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat pe insula respectivă.
Cerințe
a. Să se determine distanța maximă Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.
Date de intrare
Fișierul de intrare dragoni2.in conține pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se găsesc două numere naturale N și M reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc N numere naturale, al i-lea dintre acestea reprezentând distanța maximă Dmaxi pe care o poate zbura un dragon de pe insula i. Pe următoarele M linii sunt descrise cele M rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale A, B și D cu semnificația că există rută bidirecțională de lungime D între insulele A și B.
Date de ieșire
In fișierul de ieșire dragoni2.out se va afișa un singur număr natural.
Dacă valoarea lui p este 1, se va rezolva numai cerința a.
În acest caz numărul afișat va reprezenta distanța maximă Dmaxi a unui dragon i la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
Dacă valoarea lui p este 2, se va rezolva numai cerința b.
În acest caz numărul afișat va reprezenta distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.
Restricții
- 1 ≤ N ≤ 800
- 1 ≤ M ≤ 6.000
- 1 ≤ Dmaxi ≤ 50.000, pentru orice 1 ≤ i ≤ N.
- 1 ≤ Aj, Bj ≤ N, pentru orice 1 ≤ j ≤ M.
- 1 ≤ Dj ≤ 50.000, pentru orice 1 ≤ j ≤ M.
- Se garantează că Hiccup poate ajunge pe insula N.
- Se garantează că răspunsul oricărei cerințe este un număr natural mai mic decât 1.000.000.000.
- Pentru rezolvarea corectă a primei cerințe se acordă 20% din punctajul testului respectiv.
- Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 80% din punctajul testului respectiv.
Exemplu
dragoni2.in | dragoni2.out | Explicație |
---|---|---|
2 5 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14 |
28 |
p = 2 deci se va rezolva cerința b). Există N = 5 insule și M = 6 rute între ele. Pentru a parcurge o distanță minimă de 28 între insulele 1 și N, Hiccup face următorii pași:
|