#1069
Ubuntzei
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
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 | #54840373 | Utilizator | |
Fișier | ubuntzei.cpp | Dimensiune | 2.65 KB |
Data încărcării | 10 Decembrie 2024, 09:10 | Scor / rezultat | Eroare de compilare |
ubuntzei.cpp:3:3: error: invalid preprocessing directive #Algoritmul # Algoritmul lui Dijkstra pentru a calcula distanțele minime de la un nod sursă ^ ubuntzei.cpp:5:19: warning: multi-character character constant [-Wmultichar] dist = [float('inf')] * (n + 1) ^ ubuntzei.cpp:7:24: error: stray '#' in program pq = [(0, start)] # (cost, nod) ^ ubuntzei.cpp:23:3: error: invalid preprocessing directive #Rezolvarea # Rezolvarea problemei TSP folosind programare dinamică ^ ubuntzei.cpp:25:7: error: invalid preprocessing directive #dp # dp[mask][i] = distanța minimă de la start, trecând prin nodurile din masca \`mask\`, ^ # și ajungând la nodul i ^ ubuntzei.cpp:29:34: error: stray '#' in program if mask & (1 << u): # Dacă nodul u este deja vizitat ^ ubuntzei.cpp:29:13: error: stray '\304' in program if mask & (1 << u): # Dacă nodul u este deja vizitat ^ ubuntzei.cpp:29:13: error: stray '\203' in program ubuntzei.cpp:32:67: error: stray '#' in program if prev_mask and not (prev_mask & (1 << v)): # Dacă v nu a fost vizitat anterior ^ ubuntzei.cpp:32:21: error: stray '\304' in program if prev_mask and not (prev_mask & (1 << v)): # Dacă v nu a fost vizitat anterior ^ ubuntzei.cpp:32:21: error: stray '\203' in program ubuntzei.cpp:35:17: warning: multi-character character constant [-Wmultichar] ans = float('inf') ^ ubuntzei.cpp:41:7: error: invalid preprocessing directive #Citirea # Citirea datelor de intrare ^ ubuntzei.cpp:45:7: error: invalid preprocessing directive #Construirea # Construirea grafului ^ ubuntzei.cpp:52:7: error: invalid preprocessing directive #Localit # Localitățile importante: Cluj-Napoca (1), Vama Veche (n) și prietenii ^ ubuntzei.cpp:56:7: error: invalid preprocessing directive #Calcul # Calculăm distanțele minime între fiecare pereche de localități importante ^ ubuntzei.cpp:67:7: error: invalid preprocessing directive #Aplica # Aplicați Dynamic Programming pentru a rezolva TSP ^ ubuntzei.cpp:68:18: warning: multi-character character constant [-Wmultichar] dp = [[float('inf')] * important_node_count for _ in range(1 << important_node_count)] ^ ubuntzei.cpp:70:19: error: stray '#' in program dp[1][0] = 0 # Începem din Cluj-Napoca ^ ubuntzei.cpp:70:5: error: stray '\303' in program dp[1][0] = 0 # Începem din Cluj-Napoca ^ ubuntzei.cpp:70:5: error: stray '\216' in program ubuntzei.cpp:74:7: error: invalid preprocessing directive #Scriem # Scriem rezultatul ^ ubuntzei.cpp:1:1: error: 'import' does not name a type import heapq ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Ubuntzei face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.