Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="algoritm") ==
Desi nu e student in anul 1 la FMI, Por Costel s-a apucat sa studieze Algoritmica Grafurilor. Astazi, el invata despre alogritmul Bellman-Ford, care calculeaza drumurile minime de la un nod sursa (in cazul de fata, nodul 1) la toate celelalte noduri intr-un graf cu costuri. Por Costel, folosindu-si cunostintele sale minimale de informatica a reusit sa scrie urmatorul cod in C++ ce reprezinta o variatie al algoritmului Bellman-Ford:
Desi nu e student in anul 1 la FMI, Por Costel s-a apucat sa studieze Algoritmica Grafurilor. Astazi, el invata despre alogritmul Bellman-Ford, care calculeaza drumurile minime de la un nod sursa (in cazul de fata, nodul 1) la toate celelalte noduri intr-un graf orientat cu costuri. Por Costel, folosindu-si cunostintele sale minimale de informatica a reusit sa scrie urmatorul cod in C++ ce reprezinta o variatie al algoritmului Bellman-Ford:
_for (int i=1; i <= n; ++i)_
_ d[ i ] = infinit; // GUITZZZ!_
Dandu-se un graf orientat cu N noduri si M muchii, vi se cere sa afisati o ordonare a muchiilor astfel incat algoritmul Bellman-Ford scris de Por Costel sa se termine dupa doua iteratii (doar prima oara cand se intra in while() se produc modificari in vectorul d, iar a doua oara cand se intra, variabila ok ramane 1 si nu se mai intra a treia oara).
h2. Date de intrare
În fişierul de intrare $algoritm.in$ se va gasi pe prima linie <tex>T</tex>, numarul de teste.
Fiecare dintre cele T teste are formatul urmator: pe prima linie sunt doua numere <tex>N</tex> si <tex>M</tex>, numarul de noduri, respectiv numarul de muchii din graf. Urmeaza M linii ce descriu muchiile, fiecare continand exact 3 numere <tex>a</tex>, <tex>b</tex>, <tex>c</tex>, cu semnificatia ca exista o muchie de la nodul a la nodul b care are costul c.
h2. Date de ieşire
În fişierul de ieşire $algoritm.out$ se vor afisa <tex>T</tex> linii, fiecare cu cate <tex>M</tex> numere, a i-a linie va contine p permutare a indicilor muchiilor, ce reprezinta ordinea in care vor aparea in vectorul E al lui Por Costel. Muchiile se considera indexate dupa ordinea din fisierul de intrare (e.g. prima muchie citita este muchia cu indicele 1)
h2. Restricţii si Precizari
* <tex>1</tex> ≤ <tex>N</tex>, ≤ <tex>10^5^</tex>
* <tex>1</tex> ≤ <tex>M</tex> ≤ <tex>2*10^5^</tex>
* h2. Date de intrare
În fişierul de intrare $pocnitoare.in$ se va gasii pe prima linie <tex>N</tex>, <tex>A</tex>, <tex>X_1</tex> (pozitia initiala a lui Por Costel), <tex>Q</tex> (numarul de query-uri), <tex>Q_1</tex>(query-ul initial).
h2. Date de ieşire
În fişierul de ieşire $pocnitoare.out$ <tex>T</tex> linii fiecare cu cate <tex>Q_i</tex> <tex>(1</tex> ≤ <tex>i</tex> ≤ <tex>T)</tex> numere care reprezinta raspunsurile la fiecare din cele <tex>Q_i</tex> query-uri de la al <tex>i</tex>-lea test.
h2. Restricţii
* <tex>1</tex> ≤ <tex>N</tex>, <tex>A</tex>, <tex>X_1</tex> ≤ <tex>10^8^</tex>
* <tex>1</tex> ≤ <tex>Q</tex> ≤ <tex>10^5^</tex>
* h2. Date de intrare
În fişierul de intrare $pocnitoare.in$ se va gasii pe prima linie <tex>N</tex>, <tex>A</tex>, <tex>X_1</tex> (pozitia initiala a lui Por Costel), <tex>Q</tex> (numarul de query-uri), <tex>Q_1</tex>(query-ul initial).
h2. Date de ieşire
În fişierul de ieşire $pocnitoare.out$ <tex>T</tex> linii fiecare cu cate <tex>Q_i</tex> <tex>(1</tex> ≤ <tex>i</tex> ≤ <tex>T)</tex> numere care reprezinta raspunsurile la fiecare din cele <tex>Q_i</tex> query-uri de la al <tex>i</tex>-lea test.
h2. Restricţii
* <tex>1</tex> ≤ <tex>N</tex>, <tex>A</tex>, <tex>X_1</tex> ≤ <tex>10^8^</tex>
* <tex>1</tex> ≤ <tex>Q</tex> ≤ <tex>10^5^</tex>
* <tex>1</tex> ≤ <tex>costul unei muchii</tex> ≤ <tex>10^6</tex>
* Se garanteaza ca graful este conex
* Se garanteaza ca exista cel putin o muchie din nodul 1
* infinit e definit ca fiind mai mare ca orice numar intreg
* Se accepta orice solutie care respecta cerinta
h2. Exemplu
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
