Rezumat problemă

Dragoni

#1136

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 intre 1 si M, ruta j unește insulele A j și B j și are lungime D j.

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ă Dmax i. 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 insula 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 si 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 maxima 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.

OJI 2015, Clasele XI-XII

Fișiere Candale Silviu (silviu) concurs

Clasa 11 Teoria Grafurilor Parcurgerea grafurilor neorientate

Rezolvă

Detalii

Problema	Dragoni	Operații I/O	dragoni.in/dragoni.out
Limita timp	1.5 secunde	Limita memorie	Total: 32 MB / Stivă 8 MB
Id soluție	#396799	Utilizator	Potra Vlad (Monarch)
Fișier	dragoni.cpp	Dimensiune	2.20 KB
Data încărcării	10 Martie 2015, 14:13	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

dragoni.cpp: In function ‘int Dijkstra()’:
dragoni.cpp:60:11: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
     Q.push({0, {1, 1}});
           ^
dragoni.cpp:60:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
     Q.push({0, {1, 1}});
                       ^
dragoni.cpp:60:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
dragoni.cpp:71:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
                 Q.push({D[nn][cd], {nn, cd}});
                       ^
dragoni.cpp:71:45: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
                 Q.push({D[nn][cd], {nn, cd}});
                                             ^
dragoni.cpp:71:45: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
dragoni.cpp:76:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
                 Q.push({D[nn][cn], {nn, cn}});
                       ^
dragoni.cpp:76:45: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
                 Q.push({D[nn][cn], {nn, cn}});
                                             ^
dragoni.cpp:76:45: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
dragoni.cpp:81:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
                 Q.push({D[nn][nn], {nn, nn}});
                       ^
dragoni.cpp:81:45: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
                 Q.push({D[nn][nn], {nn, nn}});
                                             ^
dragoni.cpp:81:45: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
dragoni.cpp: In function ‘void Read()’:
dragoni.cpp:100:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
         G[a].push_back({b, c});
                       ^
dragoni.cpp:100:30: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
         G[a].push_back({b, c});
                              ^
dragoni.cpp:101:23: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
         G[b].push_back({a, c});
                       ^
dragoni.cpp:101:30: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
         G[b].push_back({a, c});
                              ^

Rezultat evaluare

Cum funcționează evaluarea?