Revizia anterioară Revizia următoare
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 orientat cu costuri pe muchii. 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 ). O muchie este retinuta ca un triplet cu semnficiatie ca muchia porneste de la la si are costul . 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 .
Dandu-se un graf orientat cu noduri si 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).
Date de intrare
În fişierul de intrare algoritm.in se va gasi pe prima linie , numarul de teste.
Fiecare dintre cele teste are formatul urmator: pe prima linie sunt doua numere si , numarul de noduri, respectiv numarul de muchii din graf. Urmeaza M linii ce descriu muchiile, fiecare continand exact 3 numere , , , cu semnificatia ca exista o muchie de la nodul la nodul care are costul .
Date de ieşire
În fişierul de ieşire algoritm.out se vor afisa linii, fiecare cu cate numere, a i-a linie va contine o permutare a indicilor muchiilor, ce reprezinta ordinea in care vor aparea in vectorul 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
- ≤
- ≤ ≤
- ≤ ≤
- ≤ costul unei muchii ≤
- 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 la , sau muchie de la la
Exemplu
algoritm.in | algoritm.out |
---|---|
1 4 4 1 2 1 3 4 2 2 3 3 1 3 1 | 1 4 2 3 |
Explicatie
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.