Detalii evaluare: ~42524786

Detalii evaluare #42524786

Rezumat problema
Detalii
Evaluare
Ajutor

Rezumat problemă

`#1136` Dragoni

Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:

Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele A _j și B _j și are lungime D _j.

Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmax _i. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care D_j ≤ Dmax_i, indiferent de ce alte drumuri au făcut anterior.

Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:

Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i si x, bineînțeles doar dacă D_j ≤ Dmax_t.
Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat pe insula respectivă.

Cerințe:

a. Să se determine distanța maxima Dmax_i caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.

OJI 2015, Clasele XI-XII

Fișiere
Candale Silviu (silviu)
concurs

Clasa 11 Teoria Grafurilor Parcurgerea grafurilor neorientate

Rezolvă

Detalii

Problema	Dragoni	Operații I/O	`dragoni.in`/`dragoni.out`
Limita timp	1.5 secunde	Limita memorie	Total: `32 MB` / Stivă `8 MB`
Id soluție	`#42524786`	Utilizator	Gavra Daria (daria_gavra)
Fișier	dragoni.cpp	Dimensiune	2.13 KB
Data încărcării	09 Martie 2023, 08:33	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

dragoni.cpp:1:10: warning: invalid suffix on literal; C++11 requires a space between literal and identifier [-Wliteral-suffix]
 #include <bits/stdc++.h>using namespace std;

          ^
dragoni.cpp:1:25: warning: extra tokens at end of #include directive [enabled by default]
 #include <bits/stdc++.h>using namespace std;

                         ^
dragoni.cpp:2:1: error: 'ifstream' does not name a type
 ifstream fin("dragoni.in");

 ^
dragoni.cpp:3:1: error: 'ofstream' does not name a type
 ofstream fout("dragoni.out");

 ^
dragoni.cpp:5:1: error: 'vector' does not name a type
 vector<pair<int,int>> lista[805];///lista[i].first-va retine nodul in care putem merge,lista[i].second-costul nodului respectiv

 ^
dragoni.cpp:6:1: error: 'vector' does not name a type
 vector<pair<int,int>> lista2[805];

 ^
dragoni.cpp: In function 'void citire()':
dragoni.cpp:8:5: error: 'fin' was not declared in this scope
     fin>>c;

     ^
dragoni.cpp:15:9: error: 'lista' was not declared in this scope
         lista[x].push_back({y,cost});

         ^
dragoni.cpp: In function 'void bfs(int)':
dragoni.cpp:20:5: error: 'queue' was not declared in this scope
     queue<int> q;

     ^
dragoni.cpp:20:5: note: suggested alternative:
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 dragoni.cpp:1:
/usr/include/c++/4.8/bits/stl_queue.h:93:11: note:   'std::queue'
     class queue
           ^
dragoni.cpp:20:11: error: expected primary-expression before 'int'
     queue<int> q;

           ^
dragoni.cpp:20:11: error: expected ';' before 'int'
dragoni.cpp:21:5: error: 'q' was not declared in this scope
     q.push(start);

     ^
dragoni.cpp:28:24: error: 'lista' was not declared in this scope
         for(auto vecin:lista[x]){

                        ^
dragoni.cpp: At global scope:
dragoni.cpp:35:36: error: 'vector' has not been declared
 void dijkstra(int start,int dragon,vector<pair<int,int>> graf[805]){

                                    ^
dragoni.cpp:35:42: error: expected ',' or '...' before '<' token
 void dijkstra(int start,int dragon,vector<pair<int,int>> graf[805]){

                                          ^
dragoni.cpp: In function 'void dijkstra(int, int, int)':
dragoni.cpp:39:5: error: 'priority_queue' was not declared in this scope
     priority_queue<pair<int,int>> q;

     ^
dragoni.cpp:39:5: note: suggested alternative:
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 dragoni.cpp:1:
/usr/include/c++/4.8/bits/stl_queue.h:367:11: note:   'std::priority_queue'
     class priority_queue
           ^
dragoni.cpp:39:20: error: 'pair' was not declared in this scope
     priority_queue<pair<int,int>> q;

                    ^
dragoni.cpp:39:20: note: suggested alternative:
In file included from /usr/include/c++/4.8/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/4.8/bits/char_traits.h:39,
                 from /usr/include/c++/4.8/ios:40,
                 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 dragoni.cpp:1:
/usr/include/c++/4.8/bits/stl_pair.h:96:12: note:   'std::pair'
     struct pair
            ^
dragoni.cpp:39:25: error: expected primary-expression before 'int'
     priority_queue<pair<int,int>> q;

                         ^
dragoni.cpp:39:25: error: expected ';' before 'int'
dragoni.cpp:40:5: error: 'q' was not declared in this scope
     q.push({0,start});

     ^
dragoni.cpp:46:24: error: 'graf' was not declared in this scope
         for(auto vecin:graf[x]){

                        ^
dragoni.cpp: In function 'int main()':
dragoni.cpp:68:9: error: 'fout' was not declared in this scope
         fout<<maxim;

         ^
dragoni.cpp:73:35: error: 'lista' was not declared in this scope
             dijkstra(i,dragoni[i],lista);

                                   ^
dragoni.cpp:78:21: error: 'lista2' was not declared in this scope
                     lista2[i].push_back({j,dp[j]});

                     ^
dragoni.cpp:82:28: error: 'lista2' was not declared in this scope
         dijkstra(1,6000000,lista2);

                            ^
dragoni.cpp:83:9: error: 'fout' was not declared in this scope
         fout<<dp[n];

         ^

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 Dragoni 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ă.