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
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:
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; //Îmi 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 ). O muchie este reţinută ca un triplet cu semnficiaţia că muchia porneşte de la la şi are costul . Dar cel mai rău probabil este faptul că 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 .
Dându-se un graf orientat cu noduri şi 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).
Date de intrare
În fişierul de intrare algoritm.in se va găsi pe prima linie , numărul de teste.
Fiecare dintre cele teste are formatul următor: pe prima linie sunt două numere şi , numărul de noduri, respectiv numărul de muchii din graf. Urmează linii ce descriu muchiile, fiecare conţinând exact 3 numere , , , cu semnificaţia că există o muchie de la nodul la nodul care are costul .
Date de ieşire
În fişierul de ieşire algoritm.out se vor afişa linii, fiecare cu câte numere, a i-a linie va conţine o permutare a indicilor muchiilor, ce reprezintă ordinea în care vor apărea în vectorul 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).
Restricţii si Precizari
- ≤
- ≤ ≤
- ≤ ≤
- ≤ costul unei muchii ≤
- 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 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 î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.