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	#63277054	Utilizator	Gliggy Gliggy (Gliggy)
Fișier	dragoni.cpp	Dimensiune	2.49 KB
Data încărcării	24 Februarie 2026, 15:38	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

dragoni.cpp: In function 'int main()':
dragoni.cpp:70:22: error: converting to 'std::priority_queue<std::tuple<long long int, int, int>, std::vector<std::tuple<long long int, int, int> >, std::greater<std::tuple<long long int, int, int> > >::value_type {aka std::tuple<long long int, int, int>}' from initializer list would use explicit constructor 'constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int, int, int}; <template-parameter-2-2> = void; _Elements = {long long int, int, int}]'
     pq.push({0, 1, 1});

                      ^
dragoni.cpp:73:14: error: expected unqualified-id before '[' token
         auto [cost, node, dragon] = pq.top();

              ^
dragoni.cpp:76:13: error: 'cost' was not declared in this scope
         if (cost != dist[node][dragon])

             ^
dragoni.cpp:76:26: error: 'node' was not declared in this scope
         if (cost != dist[node][dragon])

                          ^
dragoni.cpp:76:32: error: 'dragon' was not declared in this scope
         if (cost != dist[node][dragon])

                                ^
dragoni.cpp:80:18: error: 'node' was not declared in this scope
         if (dist[node][node] > cost) {

                  ^
dragoni.cpp:80:32: error: 'cost' was not declared in this scope
         if (dist[node][node] > cost) {

                                ^
dragoni.cpp:82:39: error: no matching function for call to 'std::priority_queue<std::tuple<long long int, int, int>, std::vector<std::tuple<long long int, int, int> >, std::greater<std::tuple<long long int, int, int> > >::push(<brace-enclosed initializer list>)'
             pq.push({cost, node, node});

                                       ^
dragoni.cpp:82:39: note: candidates are:
In file included from /usr/include/c++/4.8/queue:64:0,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:85,
                 from dragoni.cpp:1:
/usr/include/c++/4.8/bits/stl_queue.h:496:7: note: void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::tuple<long long int, int, int>; _Sequence = std::vector<std::tuple<long long int, int, int> >; _Compare = std::greater<std::tuple<long long int, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<long long int, int, int>]
       push(const value_type& __x)
       ^
/usr/include/c++/4.8/bits/stl_queue.h:496:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const std::tuple<long long int, int, int>&}'
/usr/include/c++/4.8/bits/stl_queue.h:504:7: note: void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::tuple<long long int, int, int>; _Sequence = std::vector<std::tuple<long long int, int, int> >; _Compare = std::greater<std::tuple<long long int, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<long long int, int, int>]
       push(value_type&& __x)
       ^
/usr/include/c++/4.8/bits/stl_queue.h:504:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::tuple<long long int, int, int>, std::vector<std::tuple<long long int, int, int> >, std::greater<std::tuple<long long int, int, int> > >::value_type&& {aka std::tuple<long long int, int, int>&&}'
dragoni.cpp:86:31: error: 'node' was not declared in this scope
         for (auto &edge : adj[node]) {

                               ^
dragoni.cpp:90:27: error: 'dragon' was not declared in this scope
             if (d <= Dmax[dragon]) {

                           ^
dragoni.cpp:91:41: error: 'cost' was not declared in this scope
                 if (dist[nxt][dragon] > cost + d) {

                                         ^
dragoni.cpp:93:52: error: no matching function for call to 'std::priority_queue<std::tuple<long long int, int, int>, std::vector<std::tuple<long long int, int, int> >, std::greater<std::tuple<long long int, int, int> > >::push(<brace-enclosed initializer list>)'
                     pq.push({cost + d, nxt, dragon});

                                                    ^
dragoni.cpp:93:52: note: candidates are:
In file included from /usr/include/c++/4.8/queue:64:0,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:85,
                 from dragoni.cpp:1:
/usr/include/c++/4.8/bits/stl_queue.h:496:7: note: void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::tuple<long long int, int, int>; _Sequence = std::vector<std::tuple<long long int, int, int> >; _Compare = std::greater<std::tuple<long long int, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<long long int, int, int>]
       push(const value_type& __x)
       ^
/usr/include/c++/4.8/bits/stl_queue.h:496:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const std::tuple<long long int, int, int>&}'
/usr/include/c++/4.8/bits/stl_queue.h:504:7: note: void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::tuple<long long int, int, int>; _Sequence = std::vector<std::tuple<long long int, int, int> >; _Compare = std::greater<std::tuple<long long int, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<long long int, int, int>]
       push(value_type&& __x)
       ^
/usr/include/c++/4.8/bits/stl_queue.h:504:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::tuple<long long int, int, int>, std::vector<std::tuple<long long int, int, int> >, std::greater<std::tuple<long long int, int, int> > >::value_type&& {aka std::tuple<long long int, int, int>&&}'

Cum funcționează evaluarea?