== include(page="template/taskheader" task_id="algoritm") ==

Deşi nu e student în anul 1 la FMI, Por Costel s-a apucat să studieze Algoritmica Grafurilor. Astăzi, el învaţă despre alogritmul Bellman-Ford, care calculeaza drumurile minime de la un nod sursă (in cazul de faţă, nodul 1) la toate celelalte noduri într-un graf orientat, cu costuri pe muchii. Por Costel, folosindu-şi cunoştinţele sale minimale de informatică a reuşit să scrie următorul cod in C++ ce reprezintă o variaţie 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:

==code(cpp) |

for (int i = 1; i <= n; ++i)

for (int i=1; i <= n; ++i)

         d[ i ] = infinit;  		// GUITZZZ!
d[ 1 ] = 0;

{
     ok = 1;

     for (int i=0; i < E.size(); ++i)      		        // OINC!

     for (int i=0; i<E.size(); ++i)      		        // OINC!

     {
           if  (d[ E[i].x ] + E[i].cost < d[ E[i].y ] )
           {
                 ok = 0;

                 d[ E[i].y ] = d[ E[i].x ] + E[i].cost;  		//Îmi place porumbul!

                 d[ E[i].y ] = d[ E[i].x ] + E[i].cost;  		//Imi place porumbul!

           }
     }
}
==

Observăm mai multe deficienţe în codul de mai sus. Pe lângă documentaţia rudimentară, mai avem faptul că Por Costel işi reţine graful printr-un vector de muchii (vectorul <tex>E</tex>). O muchie este reţinută ca un triplet <tex>(x,y,cost)</tex> cu semnficiaţia că muchia porneşte de la <tex>x</tex> la <tex>y</tex> şi are costul <tex>cost</tex>. Dar cel mai rău probabil este faptul că programul este LENT !

Observam mai multe deficiente in codul de mai sus. Pe langa documentatia rudimentara, mai avem faptul ca Por Costel isi retine graful printr-un vector de muchii (vectorul E). O muchie este retinuta ca un triplet (x, y, z) cu semnficiatie ca muchia porneste de la x la y si are costul z. Dar cel mai rau probabil este faptul ca programul este LENT !

Pentru că vrem ca prietenul nostru cu copite sa plece cu o părere bună despre informatică, am vrea să ia 100 de puncte cu această sursă, ba chiar să ruleze cât mai repede. Este clar că numărul de iteraţii ale _while()-ului_ este influenţat direct de ordinea muchiilor in vectorul de muchii <tex>E</tex>.

Pentru ca vrem ca prietenul nostru cu copite sa plece cu o parere buna despre informatica, am vrea sa ia 100 de puncte cu aceasta sursa, ba chiar sa ruleze cat mai repede. Este clar ca numarul de iteratii ale while-ului este influentat direct de ordinea muchiilor in vectorul de muchii E.

Dându-se un graf orientat cu <tex>N</tex> noduri şi <tex>M</tex> muchii, vi se cere să afisaţi o ordonare a muchiilor astfel incât algoritmul Bellman-Ford scris de Por Costel să se termine după exact două iteraţii (adică să se intre în instrucţiunea repetitivă _while()_ doar de două ori).

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 (adica sa se intre in instructiunea repetitiva while() doar de doua ori).

h2. Date de intrare

În fişierul de intrare $algoritm.in$ se va găsi pe prima linie <tex>T</tex>, numărul de teste.
Fiecare dintre cele <tex>T</tex> teste are formatul următor: pe prima linie sunt două numere <tex>N</tex> şi <tex>M</tex>, numărul de noduri, respectiv numărul de muchii din graf. Urmează <tex>M</tex> linii ce descriu muchiile, fiecare conţinând exact 3 numere <tex>a</tex>, <tex>b</tex>, <tex>c</tex>, cu semnificaţia că există o muchie de la nodul <tex>a</tex> la nodul <tex>b</tex> care are costul <tex>c</tex>.

Î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 afişa <tex>T</tex> linii, fiecare cu câte <tex>M</tex> numere, a i-a linie va conţine o permutare a indicilor muchiilor, ce reprezintă ordinea în care vor apărea în vectorul <tex>E</tex> al lui Por Costel. Muchiile se consideră indexate după ordinea din fişierul de intrare (e.g. prima muchie citită este muchia cu indicele 1).

Î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 o 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>T</tex> &le; <tex>5</tex>

* <tex>T</tex> = <tex>5</tex>

* <tex>1</tex> &le; <tex>N</tex> &le; <tex>10^5^</tex>
* <tex>1</tex> &le; <tex>M</tex> &le; <tex>2*10^5^</tex>
* <tex>1</tex> &le; costul unei muchii &le; <tex>10^6</tex>

* Se garanteaza ca exista cel puţin o muchie care iese din nodul 1
* În programul lui Por Costel, infinit e definit ca fiind mai mare ca orice număr întreg
* Se acceptă orice soluţie care respectă cerinţa
* **Atentie!** Graful poate conţine două muchii de la <tex>x</tex> la <tex>y</tex>, sau muchie de la <tex>x</tex> la <tex>x</tex>

* Se garanteaza ca graful este conex
* Se garanteaza ca exista cel putin o muchie care iese din nodul 1
* In programul lui Por Costel, infinit e definit ca fiind mai mare ca orice numar intreg
* Se accepta orice solutie care respecta cerinta
* Atentie ! Graful poate contine doua muchii de la x la y, sau muchie de la x la x

h2. Exemplu

| 1 4 2 3
|

h2. Explicatie

== include(page="template/taskfooter" task_id="algoritm") ==

Ordinea muchiilor in vectorul E a lui Por Costel va fi în acest caz: (1, 2, 1), (1, 3, 1), (3, 4, 2), (2, 3, 3). Se poate testa că algoritmul se va finaliza în două iteraţii. Există mai multe soluţii care ar putea fi afişate. Un alt exemplu este: 1 3 4 2.

h2. Explicatie

== include(page="template/taskfooter" task_id="algoritm") ==

Ordinea muchiilor in vectorul E a lui Por Costel va fi in acest caz: (1, 2, 1), (1, 3, 1), (3, 4, 2), (2, 3, 3). Se poate testa ca algoritmul se va finaliza in doua iteratii. Exista mai multe solutii care putea fi afisate. Un alt exemplu este: 1 3 4 2.
 

10324