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	#56541486	Utilizator	Saveliev Iulian (Julius)
Fișier	ubuntzei.cpp	Dimensiune	3.72 KB
Data încărcării	24 Februarie 2025, 20:12	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

ubuntzei.cpp: In function 'std::vector<long long int> dijkstra(int, const std::vector<std::vector<Edge> >&)':
ubuntzei.cpp:19:14: error: expected unqualified-id before '[' token
         auto [currentDist, u] = pq.top();

              ^
ubuntzei.cpp:22:13: error: 'currentDist' was not declared in this scope
         if (currentDist > dist[u]) continue;

             ^
ubuntzei.cpp:22:32: error: 'u' was not declared in this scope
         if (currentDist > dist[u]) continue;

                                ^
ubuntzei.cpp:24:39: error: 'u' was not declared in this scope
         for (const auto &edge : graph[u]) {

                                       ^
ubuntzei.cpp:25:33: error: 'currentDist' was not declared in this scope
             if (dist[edge.to] > currentDist + edge.cost) {

                                 ^
ubuntzei.cpp:27:49: error: no matching function for call to 'std::priority_queue<std::pair<long long int, int>, std::vector<std::pair<long long int, int> >, std::greater<std::pair<long long int, int> > >::push(<brace-enclosed initializer list>)'
                 pq.push({dist[edge.to], edge.to});

                                                 ^
ubuntzei.cpp:27:49: 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 ubuntzei.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::pair<long long int, int>; _Sequence = std::vector<std::pair<long long int, int> >; _Compare = std::greater<std::pair<long long int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<long long 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::pair<long long 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::pair<long long int, int>; _Sequence = std::vector<std::pair<long long int, int> >; _Compare = std::greater<std::pair<long long int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<long long 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::pair<long long int, int>, std::vector<std::pair<long long int, int> >, std::greater<std::pair<long long int, int> > >::value_type&& {aka std::pair<long long int, int>&&}'
ubuntzei.cpp: In function 'int main()':
ubuntzei.cpp:37:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("ubuntzei.in", "r", stdin);

                                       ^
ubuntzei.cpp:38:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("ubuntzei.out", "w", stdout);

                                         ^

Cum funcționează evaluarea?