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	#59012661	Utilizator	Pogan Alexandru-Mihail (Alex1234Boy)
Fișier	ubuntzei.cpp	Dimensiune	2.28 KB
Data încărcării	14 Septembrie 2025, 00:29	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

ubuntzei.cpp: In function 'std::vector<int> dijkstra(int)':
ubuntzei.cpp:14:65: error: wrong number of template arguments (0, should be 1)
     priority_queue<pair<int,int>, vector<pair<int,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:14:66: error: template argument 3 is invalid
     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

                                                                  ^
ubuntzei.cpp:14:71: error: invalid type in declaration before ';' token
     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

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

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

               ^
ubuntzei.cpp:18:14: error: expected unqualified-id before '[' token
         auto [cd,u] = pq.top(); pq.pop();

              ^
ubuntzei.cpp:18:36: error: request for member 'pop' in 'pq', which is of non-class type 'int'
         auto [cd,u] = pq.top(); pq.pop();

                                    ^
ubuntzei.cpp:19:12: error: 'cd' was not declared in this scope
         if(cd > d[u]) continue;

            ^
ubuntzei.cpp:19:19: error: 'u' was not declared in this scope
         if(cd > d[u]) continue;

                   ^
ubuntzei.cpp:20:23: error: 'u' was not declared in this scope
         for(auto e: G[u]) {

                       ^
ubuntzei.cpp:21:26: error: 'cd' was not declared in this scope
             if(d[e.to] > cd + e.cost) {

                          ^
ubuntzei.cpp:23:20: error: request for member 'push' in 'pq', which is of non-class type 'int'
                 pq.push({d[e.to], e.to});

                    ^

Cum funcționează evaluarea?