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	#58095882	Utilizator	tony ... (Tonyy_)
Fișier	dragoni.cpp	Dimensiune	1.85 KB
Data încărcării	13 Mai 2025, 21:50	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

dragoni.cpp: In function 'void dijkstra(int, int)':
dragoni.cpp:27:75: error: wrong number of template arguments (0, should be 1)
     priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> q;

                                                                           ^
In file included from /usr/include/c++/4.8/string:48:0,
                 from /usr/include/c++/4.8/bits/locale_classes.h:40,
                 from /usr/include/c++/4.8/bits/ios_base.h:41,
                 from /usr/include/c++/4.8/ios:42,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/sstream:38,
                 from /usr/include/c++/4.8/complex:45,
                 from /usr/include/c++/4.8/ccomplex:38,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:52,
                 from dragoni.cpp:1:
/usr/include/c++/4.8/bits/stl_function.h:222:12: error: provided for 'template<class _Tp> struct std::greater'
     struct greater : public binary_function<_Tp, _Tp, bool>
            ^
dragoni.cpp:27:76: error: template argument 3 is invalid
     priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> q;

                                                                            ^
dragoni.cpp:27:80: error: invalid type in declaration before ';' token
     priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> q;

                                                                                ^
dragoni.cpp:30:7: error: request for member 'push' in 'q', which is of non-class type 'int'
     q.push(make_tuple(dist, node, dragon));

       ^
dragoni.cpp:31:14: error: request for member 'empty' in 'q', which is of non-class type 'int'
     while(!q.empty())

              ^
dragoni.cpp:33:37: error: request for member 'top' in 'q', which is of non-class type 'int'
         tie(dist, node, dragon) = q.top();

                                     ^
dragoni.cpp:34:11: error: request for member 'pop' in 'q', which is of non-class type 'int'
         q.pop();

           ^
dragoni.cpp:52:19: error: request for member 'push' in 'q', which is of non-class type 'int'
                 q.push(make_tuple(d[neighbour][dragon], neighbour, dragon));

                   ^

Cum funcționează evaluarea?