# PBinfo #1136 – Dragoni – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț 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 Aj și Bj și are lungime Dj. 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ă Dmaxi. 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: 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. 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. Date de intrare Fișierul de intrare dragoni.in conține pe prima linie numărul p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se găsesc două numere naturale N și M reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc N numere naturale, al i-lea dintre acestea reprezentând distanta maximă Dmaxi pe care o poate zbura un dragon de pe insula i. Pe următoarele M linii sunt descrise cele M rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale A, B și D cu semnificația că există rută bidirecțională de lungime D între insulele A și B. Date de ieșire n fișierul de ieșire dragoni.out se va afișa un singur număr natural. Dacă valoarea lui p este 1, se rezolvă numai cerința a. În acest caz numărul afișat va reprezenta distanța maximă Dmaxi a unui dragon i la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1. Daca valoarea lui p este 2, se va rezolva numai cerința b, În acest caz numărul afișat va reprezenta distanța minima pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N. Restricții și precizări 1 ≤ N ≤ 800 1 ≤ M ≤ 6000 1 ≤ Dmaxi ≤ 50 000, pentru orice 1 ≤ i ≤ N. 1 ≤ Aj, Bj ≤ N, pentru orice 1 ≤ j ≤ M. 1 ≤ Dj ≤ 50 000, pentru orice 1 ≤ j ≤ M. Se garantează că Hiccup poate ajunge pe insula N. Se garantează că răspunsul oricărei cerințe este un număr natural mai mic decât 109. Pentru rezolvarea corectă a primei cerințe se acordă 20% din punctajul testului respectiv. Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 80% din punctajul testului respectiv. Exemplul 1 dragoni.in 1 5 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14 dragoni.out 20 Explicație p = 1 deci se va rezolva cerința a). Există N = 5 insule si M = 6 rute între ele. Hiccup pornește de pe insula 1 având un dragon care poate zbura o distanță de maxim 6. Cu acest dragon poate ajunge doar pe insulele 1, 2, 3 si 4, întrucât pentru a ajunge pe insula 5 el ar fi obligat sa parcurgă o ruta de lungime mai mare decât 6. Distanta maxima pe care o poate zbura un dragon aflat pe insulele 1, 2, 3 sau 4 este deci 20 (dragonul de pe insula 4). Se observă că dragonul care poate zbura o distanță de 26 se afla pe insula 5 și este inaccesibil. Exemplul 1 dragoni.in 2 5 6 6 3 13 20 26 1 2 5 1 3 7 1 5 10 2 3 6 3 4 5 3 5 14 dragoni.out 28 Explicație p = 2 deci se va rezolva cerința a). Există N = 5 insule și M = 6 rute între ele. Pentru a parcurge o distanță minimă de 28 între insulele 1 și N, Hiccup face următorii pași: Zboară de pe insula 1 pe insula 2 o distanță de 5 cu dragonul din specia 1. Zboară de pe insula 2 pe insula 3 o distanță de 6 cu dragonul din specia 1. Schimbă dragonul din specia 1 cu dragonul aflat pe insula 3, care poate zbura o distanță maximă de 13. Zboară de pe insula 3 pe insula 1 o distanță de 7 cu dragonul din specia 3. Zboară de pe insula 1 pe insula 5 o distanță de 10 cu dragonul din specia 3. În total el parcurge o distanță de 5 + 6 + 7 + 10 = 28. ## Cod sursă C++ ```cpp #include #include #include using namespace std; #define maxn 810 #define maxm 6010 #define inf (1LL*1000000000*1000000000) int cer, n, m, a[maxm], b[maxm], d[maxm], dmax[maxn]; int f[maxn*maxn]; long long dist[maxn*maxn]; vector v[maxn], w[maxn]; vector > h; int getNode(int lvl, int nod) { return (lvl-1)*n+nod; } void dijkstra() { for(int i=1; i<=n*n; ++i) dist[i]=inf; dist[1]=0; h.push_back(make_pair(0, 1)); int nod; long long cdist; while(!h.empty()) { nod=h[0].second; if(nod==n*n) break; cdist=-h[0].first; pop_heap(h.begin(), h.end()); h.pop_back(); if(f[nod]) continue; f[nod]=1; int fiu, dragon = (nod-1)/n+1, node = (nod-1)%n+1; fiu = getNode(node, node); if(dist[fiu]>cdist) { dist[fiu]=cdist; h.push_back(make_pair(-dist[fiu], fiu)); push_heap(h.begin(), h.end()); } for(int i=0; icdist+w[node][i] && w[node][i]<=dmax[dragon]) { dist[fiu]=cdist+w[node][i]; h.push_back(make_pair(-dist[fiu], fiu)); push_heap(h.begin(), h.end()); } } } } int cerinta1() { int best=dmax[1]; for(int i=2; i<=n; ++i) if(dist[i]!=inf && dmax[i]>best) best=dmax[i]; return best; } int main() { freopen("dragoni.in", "r", stdin); freopen("dragoni.out", "w", stdout); scanf("%d", &cer); scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) scanf("%d", &dmax[i]); for(int i=1; i<=m; ++i) { scanf("%d%d%d", &a[i], &b[i], &d[i]); v[a[i]].push_back(b[i]); v[b[i]].push_back(a[i]); w[a[i]].push_back(d[i]); w[b[i]].push_back(d[i]); } dijkstra(); if(cer==1) printf("%d ", cerinta1()); else printf("%lld ", dist[n*n]); return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1136) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1136/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1136/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)