Rezumat problemă

Dragoni

#1136

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 Dj ≤ Dmaxi, 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:

1. 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ă Dj ≤ Dmaxt.
2. 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 Dmaxi 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	#64937031	Utilizator	Ianis . (Ianis_Badita)
Fișier	dragoni.cpp	Dimensiune	2.13 KB
Data încărcării	17 Iunie 2026, 11:08	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

dragoni.cpp:82:16: warning: missing terminating " character
   82 |         printf("%d
      |                ^
dragoni.cpp:82:16: error: missing terminating " character
   82 |         printf("%d
      |                ^~~
dragoni.cpp:83:1: warning: missing terminating " character
   83 | ", cerinta1());
      | ^
dragoni.cpp:83:1: error: missing terminating " character
   83 | ", cerinta1());
      | ^~~~~~~~~~~~~~~
dragoni.cpp:85:16: warning: missing terminating " character
   85 |         printf("%lld
      |                ^
dragoni.cpp:85:16: error: missing terminating " character
   85 |         printf("%lld
      |                ^~~~~
dragoni.cpp:86:1: warning: missing terminating " character
   86 | ", dist[n*n]);
      | ^
dragoni.cpp:86:1: error: missing terminating " character
   86 | ", dist[n*n]);
      | ^~~~~~~~~~~~~~
dragoni.cpp: In function ‘void dijkstra()’:
dragoni.cpp:44:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   44 |         for(int i=0; i<v[node].size(); ++i)
      |                      ~^~~~~~~~~~~~~~~
dragoni.cpp: In function ‘int main()’:
dragoni.cpp:84:5: error: expected primary-expression before ‘else’
   84 |     else
      |     ^~~~
dragoni.cpp:66:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |     freopen("dragoni.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dragoni.cpp:67:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |     freopen("dragoni.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragoni.cpp:68:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |     scanf("%d", &cer);
      |     ~~~~~^~~~~~~~~~~~
dragoni.cpp:69:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
dragoni.cpp:71:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |         scanf("%d", &dmax[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
dragoni.cpp:74:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |         scanf("%d%d%d", &a[i], &b[i], &d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Cum funcționează evaluarea?