Fişierul intrare/ieşire:	algoritm.in, algoritm.out	Sursă	ONIS 2015, Runda 1
Autor	Mihai Nitu	Adăugată de	UNIBUC Impaler-009 Challenge costyv87 •The_Viper_The_Mountain_And_The_Imp
Timp execuţie pe test	1.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Por Costel si Algoritmul

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:

for (int i=1; i <= n; ++i)
  d[ i ] = infinit;  // GUITZZZ!
d[ 1 ] = 0;

bool ok = 0;

while (ok == 0)
{
  ok = 1;

  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;  //Imi place porumbul!
  }
}

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). Dar cel mai rau probabil este faptul ca algoritmul este LENT !

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.

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).

Exemplu

Explicaţie

...

Cum se trimit solutii?