Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-02-17 11:50:44.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:algoritm.in, algoritm.outSursăONIS 2015, Runda 1
AutorMihai NituAdăugată deThe_Viper_The_Mountain_And_The_ImpUNIBUC Impaler-009 Challenge costyv87 The_Viper_The_Mountain_And_The_Imp
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 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!
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 programul 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).

Date de intrare

În fişierul de intrare algoritm.in se va gasi pe prima linie T, numarul de teste.
Fiecare dintre cele T teste are formatul urmator: pe prima linie sunt doua numere N si M, numarul de noduri, respectiv numarul de muchii din graf. Urmeaza M linii ce descriu muchiile, fiecare continand exact 3 numere a, b, c, cu semnificatia ca exista o muchie de la nodul a la nodul b care are costul c.

Date de ieşire

În fişierul de ieşire algoritm.out se vor afisa T linii, fiecare cu cate M 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)

Restricţii si Precizari

  • T = 5
  • 1N10^5^
  • 1M2*10^5^
  • 1 ≤ costul unei muchii ≤ 10^6
  • 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

Exemplu

algoritm.inalgoritm.out
1
4 4
1 2 1
3 4 2
2 3 3
1 3 1
1 4 2 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?