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. 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. O muchie este retinuta ca un triplet (x, y, z) cu semnficiatie ca muchia porneste de la x la y si are costul z.
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 , numarul de teste.
Fiecare dintre cele T 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 a la nodul b care are costul c.
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 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
- =
- ≤ ≤
- ≤ ≤
- ≤ costul unei muchii ≤
- 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.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.