Fişierul intrare/ieşire:dragoni2.in, dragoni2.outSursăOJI 2015 clasele 11-12
AutorVlad-Alexandru GavrilaAdăugată deheracleRadu Muntean heracle
Timp execuţie pe test0.2 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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:

  1. 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.
  2. 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.indragoni2.outExplicaţie
1
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
20
p = 1 deci se va rezolva cerinţa a).
Există N = 5 insule si M = 6 rute între ele. Hiccup porneşte de pe insula 1 având un dragon
care poate zbura o distanţă de maxim 6. Cu acest dragon poate ajunge doar pe insulele 1, 2, 3 si 4,
întrucât pentru a ajunge pe insula 5 el ar fi obligat să parcurgă o rută de lungime mai mare decât 6.
Distanţa maximă pe care o poate zbura un dragon aflat pe insulele 1, 2, 3 sau 4 este deci 20
(dragonul de pe insula 4). Se observă că dragonul care poate zbura o distanţă de 26 se află
pe insula 5 şi este inaccesibil.
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:
* Zboară de pe insula 1 pe insula 2 o distanţă de 5 cu dragonul din specia 1.
* Zboară de pe insula 2 pe insula 3 o distanţă de 6 cu dragonul din specia 1.
* Schimbă dragonul din specia 1 cu dragonul aflat pe insula 3, care poate zbura o distanţă maximă de 13.
* Zboară de pe insula 3 pe insula 1 o distanţă de 7 cu dragonul din specia 3.
* Zboară de pe insula 1 pe insula 5 o distanţă de 10 cu dragonul din specia 3.
În total el parcurge o distanţă de 5 + 6 + 7 + 10 = 28.
Trebuie sa te autentifici pentru a trimite solutii. Click aici