Fișierul intrare/ieșire dragoni2.in, dragoni2.out Sursă OJI 2015 clasele 11-12
Autor Vlad-Alexandru Gavrilă Adăugată de avatar heracle 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.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:
  • 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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii