# PBinfo #4411 – veri – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț Se dă un graf orientat cu n noduri și m muchii. Fiecare muchie are costul 1 (poate fi parcursă într-un minut). Doi “prieteni” (veri) pornesc din nodul S. Unul dintre ei vrea să ajungă în nodul A, iar celălalt vrea să ajungă în nodul B. Cei doi prieteni se vor plimba împreună până când ciclează, adică până când vor ajunge în același nod a doua oară, notat cu Z. După ciclare, ei își pot continua drumurile separat. Totuși, dacă vor, pot să meargă amândoi în continuare pe același drum:~doar dispare obligația de a merge împreună. Fiecare dintre ei trebuie să-și termine drumul doar după ciclare, adică după ce nu mai sunt obligați să meargă împreună. Totuși, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în A sau B). Cerința Care este numărul minim de minute necesar, astfel încât să fie posibil ca amândoi să ajungă la destinațiile lor, în timpul alocat, în A, respectiv B? Cu alte cuvinte, dacă cei doi veri ciclează pentru prima oară după exact t minute, apoi își continuă drumurile pentru alte tA, respectiv tB minute, vrem să aflăm valoarea minimă a lui max(t + tA, t + tB). Există două tipuri de cerințe, reprezentate printr-un număr c: Dacă c = 1, trebuie calculată valoarea minimă a lui max(t + tA, t + tB). Dacă c = 2, trebuie afișat un triplet de drumuri care poate fi urmat de cei doi veri (drumul comun din S până în Z, drum urmat ulterior de primul văr din Z până în A, drum urmat ulterior de al doilea văr din Z până în B), astfel încât valoarea asociată drumurilor, adică max(t + tA, t + tB) să fie minimă. Orice triplet corect cu valoarea asociată minimă poate fi afișat. Date de intrare Pe prima linie a fișierului de intrare veri.in se găsește c. Pe a doua linie se găsesc doi întregi n și m. Pe a treia linie se găsesc trei întregi S, A și B. Pe următoarele m linii se găsesc câte doi întregi X și Y, reprezentând că există o muchie direcționată de la nodul X la nodul Y, care poate fi parcursă într-un minut (de cost 1). Date de ieșire Fișierul de ieșire este veri.out. Dacă c = 1, afișați un singur număr, valoarea minimă a lui max(t + tA, t + tB). Dacă c = 2, afișati trei drumuri. Primul drum este format de la S până la Z. Al doilea drum este format de la Z până la A. Al treilea drum este format de la Z până la B, unde S, A, B, Z sunt definite anterior. Fiecare drum se va tipări pe două linii separate. Pe prima linie va apărea lungimea drumului, adică numărul de muchii. Pe a doua linie vor apărea nodurile drumului, separate prin câte un spațiu. Valoarea asociată drumurilor, adică max(t + tA, t + tB), trebuie să fie minimă. Restricții și precizări 1 ≤ S, A, B, Z ≤ n ≤ 5000. Nodurile sunt numerotate de la 1 la n. A ≠ B 1 ≤ m ≤ n(n − 1) Se garantează că pentru orice test dat spre rezolvare există cel puțin o soluție. Nu există muchii de la un nod la el însuși. Există maxim o muchie orientată între oricare două noduri distincte. Dacă verii se despart în A, primul văr poate să nu mai facă nimic (drumul lui ulterior ar avea 0 muchii și l-ar conține doar pe A: vezi exemplul 3). Analog pentru B. Pentru fiecare subtask, testele cu c = 1 vor conta pentru 60% din punctaj. Exemplul 1: veri.in 2 7 8 1 3 4 1 2 2 5 5 7 7 6 6 7 6 5 5 3 7 4 veri.out 5 1 2 5 7 6 5 1 5 3 2 5 7 4 Explicație Drumul urmat în comun de cei doi este 1 → 2 → 5 → 7 → 6 → 5. Drumul urmat de primul văr în continuare este 5 → 3. Drumul continuat de al doilea văr este 5 → 7 → 4. Astfel, primul văr are nevoie de 6 minute pentru a ajunge în A, iar al doilea de 7 minute pentru a ajunge în B, deci răspunsul pentru c = 1 este 7. Cei doi ar fi putut să cicleze în 7, dacă ar fi urmat drumul 1 → 2 → 5 → 7 → 6 → 7. Totuși, deși al doilea văr ar fi ajuns în B în doar 6 minute (7 → 4), primul văr ar fi avut nevoie de cel puțin 8 minute ca să ajungă în A (7 → 6 → 5 → 3). Exemplul 2: veri.in 2 7 8 1 2 5 1 3 1 4 3 2 4 5 6 4 7 3 3 6 4 7 veri.out 5 1 4 7 3 6 4 3 4 7 3 2 1 4 5 Explicație Răspunsul corect pentru c = 1 este 8. Pentru acest exemplu există două soluții corecte. A doua soluție este tripletul de drumuri (1 → 3 → 6 → 4 → 7 → 3, 3 → 2, 3 → 6 → 4 → 5). Exemplul 3: veri.in 2 5 6 1 3 5 1 2 2 3 3 4 4 3 3 1 3 5 veri.out 4 1 2 3 4 3 0 3 1 3 5 Explicație Răspunsul corect pentru c = 1 este 5. Este folosit un ciclu care se termină în A = 3. Exemplul 4: veri.in 1 4 4 1 2 4 1 3 3 2 2 3 2 4 veri.out 5 Explicație Pentru c = 2, singurul triplet corect de drumuri este (1 → 3 → 2 → 3, 3 → 2, 3 → 2 → 4). Atenție! Tripletul (1 → 3 → 2 → 3 → 2, 2, 2 → 4) este greșit, deoarece primul nod vizitat a doua oară nu este 2. ## Cod sursă C++ ```cpp #include #define ll long long #define pii pair #define pli pair #define pil pair #define pll pair #define fi first #define se second #define inf (INT_MAX/2-1) #define infl (1LL<<61) #define vi vector #define vl vector #define pb push_back #define sz(a) ((int)(a).size()) #define all(a) begin(a),end(a) #define y0 y5656 #define y1 y7878 #define aaa (void)system("read -r -p \"Press enter to continue...\" key"); #define dbg(x) std::cerr<<(#x)<<": "<<(x)<<'\n',aaa #define dbga(x,n) std::cerr<<(#x)<<"[]: ";for(int _=0;_ qu; fill(d+1, d+n+1, inf); fill(p+1, p+n+1, -1); d[src] = 0; qu.push(src); while (!qu.empty()) { int nod = qu.front(); qu.pop(); for (int nn: gh[nod]) { if (d[nn] > d[nod] + 1) { d[nn] = d[nod] + 1; p[nn] = nod; qu.push(nn); } } } } vi genWay(int *p, int src, int dst, bool inv = true) { vi sol(1, dst); while (sol.back() != src) { sol.pb(p[sol.back()]); } if (inv) { reverse(all(sol)); } return sol; } void afis(vi x) { assert(sz(x) > 0); fout << sz(x) - 1 << '\n'; for (int y: x) fout << y << ' '; fout << '\n'; } int main() { int tip; fin >> tip; int n, m; fin >> n >> m; int s, a, b; fin >> s >> a >> b; int i, j, z; for (i = 1; i <= m; i++) { int x, y; fin >> x >> y; g[x].pb(y); gt[y].pb(x); } bf(n, s, g, ds, prewS); if (a == b) { if (tip == 1) { fout << ds[a]; } else { afis(genWay(prewS, s, a)); afis({a}); afis({a}); } return 0; } bf(n, a, gt, da, prewA); bf(n, b, gt, db, prewB); int ans = inf, ansCyc = inf, bestI = -1, bestJ = -1; for (i = 1; i <= n; i++) { ///s -> i -> (ciclu) -> i -> a/b. if (ds[i] < inf && da[i] < inf && db[i] < inf) { bf(n, i, g, d, prew); for (int nn: gt[i]) { if (d[nn] < inf && ans > ds[i] + d[nn] + 1 + max(da[i], db[i]) || (ans == ds[i] + d[nn] + 1 + max(da[i], db[i]) && ansCyc > ds[i] + d[nn] + 1)) { ans = ds[i] + d[nn] + 1 + max(da[i], db[i]); ansCyc = ds[i] + d[nn] + 1; ///poate am s -> .. j .. -> i -> (ciclu care trece si prin j?) -> i -> a/b. bestI = i; bestJ = nn; } } } } if (tip == 1) { fout << ans; } else { bf(n, bestI, g, d, prew); vi waySI = genWay(prewS, s, bestI); waySI.pop_back(); vi wayII = genWay(prew, bestI, bestJ); wayII.pb(bestI); waySI.insert(waySI.end(), all(wayII)); afis(waySI); afis(genWay(prewA, a, bestI, false)); afis(genWay(prewB, b, bestI, false)); } return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4411) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4411/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4411/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)