Rezumat problemă

Ubuntzei

#1069

Trei ubuntzei au hotărât ca anul acesta să petreacă ziua de 1 Mai pe malul Mării Negre împreună cu prietenii lor, motiv pentru care au pus la cale o excursie pe un traseu care să plece din oraşul lor Cluj-Napoca spre Vama Veche, unde nisipul îi aşteaptă.

În ţara ubuntzeilor există N localităţi, numerotate de la 1 la N, legate între ele prin M şosele bidirecţionale de diferite lungimi. Localitatea de plecare a ubuntzeilor, oraşul Cluj-Napoca, este numerotată cu 1, iar localitatea destinaţie, Vama Veche, cu N. Între oricare două localităţi există cel mult o şosea. Fiecare şosea uneşte două localităţi distincte şi se poate călători între oricare două localităţi circulând numai pe şosele.
Prietenii ubuntzeilor locuiesc în K localităţi distincte, diferite de Cluj-Napoca şi Vama Veche. Pentru a nu călători singuri, cei trei ubuntzei vor să treacă prin cele K localităţi în care locuiesc prietenii lor, şi apoi, împreună cu aceştia, să-şi continue excursia către mare.

Nerăbdători să ajungă cât mai repede la destinaţie, ubuntzeii s-au hotărât să îşi stabilească un traseu de lungime minimă care să treacă prin toate cele K localităţi.

Scrieţi un program care să determine, pentru ubuntzei, lungimea minimă L a unui traseu de la Cluj-Napoca la Vama Veche ce trece prin toate cele K localităţi.

OJI 2011, Clasele XI-XII

Fișiere Candale Silviu (silviu) Marius Stroe concurs

Clasa 11 Teoria Grafurilor Grafuri cu costuri Algoritmul lui Dijkstra Programare dinamica pe stari exponentiale

Rezolvă

Detalii

Problema	Ubuntzei	Operații I/O	ubuntzei.in/ubuntzei.out
Limita timp	1 secunde	Limita memorie	Total: 32 MB / Stivă 20 MB
Id soluție	#63367454	Utilizator	Negrila Florin (Florin27894)
Fișier	ubuntzei.cpp	Dimensiune	1.55 KB
Data încărcării	28 Februarie 2026, 11:12	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

ubuntzei.cpp: In function 'int main()':
ubuntzei.cpp:26:101: error: wrong number of template arguments (0, should be 1)
     priority_queue<tuple<long long, int, set<int>>, vector<tuple<long long, int, set<int>>>, greater<>> pq;

                                                                                                     ^
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 ubuntzei.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>
            ^
ubuntzei.cpp:26:102: error: template argument 3 is invalid
     priority_queue<tuple<long long, int, set<int>>, vector<tuple<long long, int, set<int>>>, greater<>> pq;

                                                                                                      ^
ubuntzei.cpp:26:107: error: invalid type in declaration before ';' token
     priority_queue<tuple<long long, int, set<int>>, vector<tuple<long long, int, set<int>>>, greater<>> pq;

                                                                                                           ^
ubuntzei.cpp:33:8: error: request for member 'push' in 'pq', which is of non-class type 'int'
     pq.push({0, 1, s});

        ^
ubuntzei.cpp:35:15: error: request for member 'empty' in 'pq', which is of non-class type 'int'
     while(!pq.empty())

               ^
ubuntzei.cpp:37:14: error: expected unqualified-id before '[' token
         auto [cost, curr, viz] = pq.top();

              ^
ubuntzei.cpp:38:12: error: request for member 'pop' in 'pq', which is of non-class type 'int'
         pq.pop();

            ^
ubuntzei.cpp:39:17: error: 'curr' was not declared in this scope
         if(dist[curr].count(viz) && cost > dist[curr][viz])

                 ^
ubuntzei.cpp:39:29: error: 'viz' was not declared in this scope
         if(dist[curr].count(viz) && cost > dist[curr][viz])

                             ^
ubuntzei.cpp:39:37: error: 'cost' was not declared in this scope
         if(dist[curr].count(viz) && cost > dist[curr][viz])

                                     ^
ubuntzei.cpp:41:18: error: expected unqualified-id before '[' token
         for(auto [next, w] : G[curr])

                  ^
ubuntzei.cpp:41:18: error: expected ';' before '[' token
ubuntzei.cpp:41:25: error: 'w' was not declared in this scope
         for(auto [next, w] : G[curr])

                         ^
ubuntzei.cpp: In lambda function:
ubuntzei.cpp:41:28: error: expected '{' before ':' token
         for(auto [next, w] : G[curr])

                            ^
ubuntzei.cpp: In function 'int main()':
ubuntzei.cpp:41:18: error: overloaded function with no contextual type information
         for(auto [next, w] : G[curr])

                  ^
ubuntzei.cpp:41:28: error: expected ';' before ':' token
         for(auto [next, w] : G[curr])

                            ^
ubuntzei.cpp:41:28: error: expected primary-expression before ':' token
ubuntzei.cpp:41:28: error: expected ')' before ':' token
ubuntzei.cpp:41:28: error: expected primary-expression before ':' token
ubuntzei.cpp:41:28: error: expected ';' before ':' token
ubuntzei.cpp:62:1: error: expected '}' at end of input
 }

 ^
ubuntzei.cpp:62:1: error: expected '}' at end of input

Cum funcționează evaluarea?