Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.
Detalii evaluare #63391441
Rezumat problemă
#588
Se dă un graf orientat ponderat – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod p. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la p la fiecare nod al grafului.
Candale Silviu (silviu) Detalii
| Problema | Dijkstra | Operații I/O |
dijkstra.in/dijkstra.out
|
|---|---|---|---|
| Limita timp | 0.1 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
| Id soluție | #63391441 | Utilizator |
Mancas Casian (Casian_Mancas)
|
| Fișier | dijkstra.cpp | Dimensiune | 4.88 KB |
| Data încărcării | 01 Martie 2026, 16:11 | Scor/rezultat | Eroare de compilare |
Evaluare
Mesaj compilare
dijkstra.cpp:49:1: error: stray '\342' in program You initialize d[0] = INF so that node 0 acts as a "sentinel" in the pmax search — but f[0] is never set to true, so node 0 can be picked as pmax when all remaining nodes are already finalized or unreachable. You should either initialize d[0] = INF and f[0] = true from the start, or better yet, just start pmax search from 1 and track it differently. ^ dijkstra.cpp:49:1: error: stray '\200' in program dijkstra.cpp:49:1: error: stray '\224' in program dijkstra.cpp:55:124: warning: missing terminating ' character [enabled by default] You manually relax adj[s] before the loop, then the loop will also process pmax = s... except f[s] = true already, so s won't be picked again. Actually this part is fine, but the manual pre-relaxation is redundant — the loop handles it. Not a bug, just unnecessary. ^ dijkstra.cpp:55:1: error: missing terminating ' character You manually relax adj[s] before the loop, then the loop will also process pmax = s... except f[s] = true already, so s won't be picked again. Actually this part is fine, but the manual pre-relaxation is redundant — the loop handles it. Not a bug, just unnecessary. ^ dijkstra.cpp:57:103: warning: missing terminating ' character [enabled by default] 3. If pmax remains 0 after the search, you mark f[0] = true and process adj[0] (which is empty), so it's harmless if you add f[0] = true — but without it, you loop infinitely selecting node 0. ^ dijkstra.cpp:57:1: error: missing terminating ' character 3. If pmax remains 0 after the search, you mark f[0] = true and process adj[0] (which is empty), so it's harmless if you add f[0] = true — but without it, you loop infinitely selecting node 0. ^ dijkstra.cpp:64:1: error: stray '\342' in program Cleaner version — remove the redundant pre-relaxation and fix the sentinel: ^ dijkstra.cpp:64:1: error: stray '\200' in program dijkstra.cpp:64:1: error: stray '\224' in program dijkstra.cpp:86:1: error: stray '\342' in program Cu fix-ul f[0] = true — da, merge. ^ dijkstra.cpp:86:1: error: stray '\200' in program dijkstra.cpp:86:1: error: stray '\224' in program dijkstra.cpp:88:1: error: stray '\304' in program Fără el, dacă există noduri neatinse la final, pmax rămâne 0 și marchezi f[0] = true în acea iterație, deci practic se "repară" singur după prima dată când se întâmplă asta. În practică pe majoritatea testelor probabil trece, dar e un comportament nedefinit/fragil. ^ dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\303' in program dijkstra.cpp:88:1: error: stray '\242' in program dijkstra.cpp:88:1: error: stray '\310' in program dijkstra.cpp:88:1: error: stray '\231' in program dijkstra.cpp:88:1: error: stray '\303' in program dijkstra.cpp:88:1: error: stray '\256' in program dijkstra.cpp:88:1: error: stray '\310' in program dijkstra.cpp:88:1: error: stray '\233' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\303' in program dijkstra.cpp:88:1: error: stray '\242' in program dijkstra.cpp:88:1: error: stray '\303' in program dijkstra.cpp:88:1: error: stray '\256' in program dijkstra.cpp:88:1: error: stray '\303' in program dijkstra.cpp:88:1: error: stray '\242' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:88:1: error: stray '\303' in program dijkstra.cpp:88:1: error: stray '\216' in program dijkstra.cpp:88:1: error: stray '\304' in program dijkstra.cpp:88:1: error: stray '\203' in program dijkstra.cpp:90:1: error: stray '\304' in program Codul tău original funcționează corect atâta timp cât graful este conex — atunci pmax nu va rămâne niciodată 0 în primele n-1 iterații. Dacă graful nu e conex, poate da rezultate greșite. ^ dijkstra.cpp:90:1: error: stray '\203' in program dijkstra.cpp:90:1: error: stray '\310' in program dijkstra.cpp:90:1: error: stray '\233' in program dijkstra.cpp:90:1: error: stray '\304' in program dijkstra.cpp:90:1: error: stray '\203' in program dijkstra.cpp:90:1: error: stray '\303' in program dijkstra.cpp:90:1: error: stray '\242' in program dijkstra.cpp:90:1: error: stray '\303' in program dijkstra.cpp:90:1: error: stray '\242' in program dijkstra.cpp:90:1: error: stray '\342' in program dijkstra.cpp:90:1: error: stray '\200' in program dijkstra.cpp:90:1: error: stray '\224' in program dijkstra.cpp:90:1: error: stray '\304' in program dijkstra.cpp:90:1: error: stray '\203' in program dijkstra.cpp:90:1: error: stray '\303' in program dijkstra.cpp:90:1: error: stray '\242' in program dijkstra.cpp:90:1: error: stray '\304' in program dijkstra.cpp:90:1: error: stray '\203' in program dijkstra.cpp:90:1: error: stray '\303' in program dijkstra.cpp:90:1: error: stray '\256' in program dijkstra.cpp:90:1: error: stray '\310' in program dijkstra.cpp:90:1: error: stray '\233' in program dijkstra.cpp:90:1: error: stray '\304' in program dijkstra.cpp:90:1: error: stray '\203' in program dijkstra.cpp:90:1: error: stray '\310' in program dijkstra.cpp:90:1: error: stray '\231' in program dijkstra.cpp:102:1: error: stray '\303' in program Atât. Fix minimal, restul codului rămâne neschimbat. ^ dijkstra.cpp:102:1: error: stray '\242' in program dijkstra.cpp:102:1: error: stray '\304' in program dijkstra.cpp:102:1: error: stray '\203' in program dijkstra.cpp:102:1: error: stray '\303' in program dijkstra.cpp:102:1: error: stray '\242' in program dijkstra.cpp:107:1: error: stray '\303' in program Înlocuiești auto cu tipurile explicite: ^ dijkstra.cpp:107:1: error: stray '\216' in program dijkstra.cpp:107:1: error: stray '\310' in program dijkstra.cpp:107:1: error: stray '\231' in program dijkstra.cpp:113:1: error: stray '\310' in program și ^ dijkstra.cpp:113:1: error: stray '\231' in program dijkstra.cpp:120:1: error: stray '\304' in program auto[v,c] e structured bindings din C++17. Dacă compilatorul e mai vechi, folosești .first și .second în loc. ^ dijkstra.cpp:120:1: error: stray '\203' in program dijkstra.cpp:120:1: error: stray '\310' in program dijkstra.cpp:120:1: error: stray '\231' in program dijkstra.cpp:120:1: error: stray '\310' in program dijkstra.cpp:120:1: error: stray '\231' in program dijkstra.cpp:120:1: error: stray '\303' in program dijkstra.cpp:120:1: error: stray '\256' in program dijkstra.cpp:124:3: error: invalid digit "8" in octal constant 4:08 PM ^ dijkstra.cpp:125:1: error: stray '\310' in program GCC 4.8 e C++11, deci auto merge dar structured bindings (auto[v,c]) nu merg. Folosești varianta cu .first și .second cum am arătat mai sus, și compilezi cu: ^ dijkstra.cpp:125:1: error: stray '\231' in program dijkstra.cpp:125:1: error: stray '\310' in program dijkstra.cpp:125:1: error: stray '\231' in program dijkstra.cpp:125:1: error: stray '\304' in program dijkstra.cpp:125:1: error: stray '\203' in program dijkstra.cpp:125:1: error: stray '\310' in program dijkstra.cpp:125:1: error: stray '\231' in program dijkstra.cpp: In function 'int main()': dijkstra.cpp:25:13: error: expected unqualified-id before '[' token for(auto[v,c]:adj[s]) { ^ dijkstra.cpp:25:13: error: expected ';' before '[' token dijkstra.cpp:25:14: error: 'v' was not declared in this scope for(auto[v,c]:adj[s]) { ^ dijkstra.cpp:25:16: error: 'c' was not declared in this scope for(auto[v,c]:adj[s]) { ^ dijkstra.cpp: In lambda function: dijkstra.cpp:25:18: error: expected '{' before ':' token for(auto[v,c]:adj[s]) { ^ dijkstra.cpp: In function 'int main()': dijkstra.cpp:25:18: error: expected ';' before ':' token dijkstra.cpp:25:18: error: expected primary-expression before ':' token dijkstra.cpp:25:18: error: expected ')' before ':' token dijkstra.cpp:25:18: error: expected primary-expression before ':' token dijkstra.cpp:25:18: error: expected ';' before ':' token dijkstra.cpp:34:18: error: expected unqualified-id before '[' token for(auto [v,c]: adj[pmax]) { ^ dijkstra.cpp:34:18: error: expected ';' before '[' token dijkstra.cpp:34:19: error: 'v' was not declared in this scope for(auto [v,c]: adj[pmax]) { ^ dijkstra.cpp:34:21: error: 'c' was not declared in this scope for(auto [v,c]: adj[pmax]) { ^ dijkstra.cpp: In lambda function: dijkstra.cpp:34:23: error: expected '{' before ':' token for(auto [v,c]: adj[pmax]) { ^ dijkstra.cpp: In function 'int main()': dijkstra.cpp:34:23: error: expected ';' before ':' token dijkstra.cpp:34:23: error: expected primary-expression before ':' token dijkstra.cpp:34:23: error: expected ')' before ':' token dijkstra.cpp:34:23: error: expected primary-expression before ':' token dijkstra.cpp:34:23: error: expected ';' before ':' token dijkstra.cpp: At global scope: dijkstra.cpp:43:1: error: 'Show' does not name a type Show more ^ dijkstra.cpp:51:27: error: 'after' does not name a type The fix: add f[0] = true; after d[0] = INF;. ^ dijkstra.cpp:51:44: error: expected unqualified-id before '.' token The fix: add f[0] = true; after d[0] = INF;. ^ dijkstra.cpp:63:1: error: 'f' does not name a type f[0] = true; // ← add this ^ dijkstra.cpp:64:1: error: 'Cleaner' does not name a type Cleaner version — remove the redundant pre-relaxation and fix the sentinel: ^ dijkstra.cpp:67:14: error: 'i' does not name a type for(int i=0; i<=n; i++) { d[i]=INF; f[i]=false; } ^ dijkstra.cpp:67:20: error: 'i' does not name a type for(int i=0; i<=n; i++) { d[i]=INF; f[i]=false; } ^ dijkstra.cpp:68:1: error: 'f' does not name a type f[0]=true; // sentinel so node 0 is never picked ^ dijkstra.cpp:69:1: error: 'd' does not name a type d[s]=0; ^ dijkstra.cpp:71:1: error: expected unqualified-id before 'for' for(int k=1; k<=n; k++) { ^ dijkstra.cpp:71:14: error: 'k' does not name a type for(int k=1; k<=n; k++) { ^ dijkstra.cpp:71:20: error: 'k' does not name a type for(int k=1; k<=n; k++) { ^ dijkstra.cpp:81:1: error: 'This' does not name a type This also adds an early exit (if(pmax==0) break) for graphs with unreachable nodes, avoiding wasted iterations. ^ dijkstra.cpp:101:1: error: 'f' does not name a type f[0]=true; // adauga asta ^ dijkstra.cpp:102:1: error: 'At' does not name a type Atât. Fix minimal, restul codului rămâne neschimbat. ^ dijkstra.cpp:113:3: error: 'i' does not name a type și ^ dijkstra.cpp:120:5: error: expected unqualified-id before '[' token auto[v,c] e structured bindings din C++17. Dacă compilatorul e mai vechi, folosești .first și .second în loc. ^ dijkstra.cpp:135:13: error: redefinition of 'std::ifstream fin' ifstream fin("dijkstra.in"); ^ dijkstra.cpp:5:10: error: 'std::ifstream fin' previously declared here ifstream fin("dijkstra.in"); ^ dijkstra.cpp:136:14: error: redefinition of 'std::ofstream fout' ofstream fout("dijkstra.out"); ^ dijkstra.cpp:6:10: error: 'std::ofstream fout' previously declared here ofstream fout("dijkstra.out"); ^ dijkstra.cpp:137:11: error: redefinition of 'const int INF' const int INF=1e9; ^ dijkstra.cpp:7:11: error: 'const int INF' previously defined here const int INF=1e9; ^ dijkstra.cpp:138:11: error: redefinition of 'const int NMAX' const int NMAX=101; ^ dijkstra.cpp:8:11: error: 'const int NMAX' previously defined here const int NMAX=101; ^ dijkstra.cpp:139:5: error: redefinition of 'int n' int n,s,v1,v2,cost; ^ dijkstra.cpp:9:5: error: 'int n' previously declared here int n,s,v1,v2,cost; ^ dijkstra.cpp:139:7: error: redefinition of 'int s' int n,s,v1,v2,cost; ^ dijkstra.cpp:9:7: error: 'int s' previously declared here int n,s,v1,v2,cost; ^ dijkstra.cpp:139:9: error: redefinition of 'int v1' int n,s,v1,v2,cost; ^ dijkstra.cpp:9:9: error: 'int v1' previously declared here int n,s,v1,v2,cost; ^ dijkstra.cpp:139:12: error: redefinition of 'int v2' int n,s,v1,v2,cost; ^ dijkstra.cpp:9:12: error: 'int v2' previously declared here int n,s,v1,v2,cost; ^ dijkstra.cpp:139:15: error: redefinition of 'int cost' int n,s,v1,v2,cost; ^ dijkstra.cpp:9:15: error: 'int cost' previously declared here int n,s,v1,v2,cost; ^ dijkstra.cpp:140:31: error: redefinition of 'std::vector<std::pair<int, int> > adj [101]' vector<pair<int,int>> adj[NMAX]; ^ dijkstra.cpp:10:23: error: 'std::vector<std::pair<int, int> > adj [101]' previously declared here vector<pair<int,int>> adj[NMAX]; ^ dijkstra.cpp:141:11: error: redefinition of 'int d [101]' int d[NMAX]; ^ dijkstra.cpp:11:5: error: 'int d [101]' previously declared here int d[NMAX]; ^ dijkstra.cpp:142:12: error: redefinition of 'bool f [101]' bool f[NMAX]; ^ dijkstra.cpp:12:6: error: 'bool f [101]' previously declared here bool f[NMAX]; ^ dijkstra.cpp: In function 'int main()': dijkstra.cpp:143:5: error: redefinition of 'int main()' int main() { ^ dijkstra.cpp:13:5: error: 'int main()' previously defined here int main() { ^ dijkstra.cpp:157:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<adj[pmax].size(); j++) { ^
Cum funcționează evaluarea?
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
- probleme la care rezolvarea presupune scrierea unui program complet
- probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.
Problema Dijkstra face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
- Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
- Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.
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ă.