Fişierul intrare/ieşire: | rf.in, rf.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Roy-Floyd
Cerinta
Micul Floyd locuieste intr-un oras mare, in care exista N intersectii. Fiecare pereche de intersectii este conectata printr-un drum bidirectional avand o lungime pozitiva data. Micul Floyd este un baiat curios si i-ar placea sa stie care este distanta minima pe care cineva ar trebui sa o parcurga de-a lungul drumurilor existente daca ar vrea sa mearga din intersectia X in intersectia Y. Deoarece ii plac foarte mult intersectiile ar vrea de asemenea sa stie, in cazul in care exista mai multe drumuri intre X si Y de aceeasi lungime minima, care este numarul maxim de strazi pe care ar putea sa mearga cineva pentru a obtine aceasta distanta minima.
Date de intrare
Prima linie a fisierului rf.in contine numarul de intersectii N. Urmatoarele N linii contin cate N numere intregi. Al j-ulea numar de pe a i-a linie reprezinta lungimea drumului dintre intersectiile i si j. Matricea data este simetrica. Intersectiile sunt numerotate cu numere intregi de la 1 la N.
Date de iesire
In fisierul rf.out afisati doua matrici de dimensiune NxN. Fiecare matrice va fi afisata pe cate N linii, fiecare continand cate N numere intregi, separate de cate un singur spatiu (fara spatii suplimentare la inceputul sau sfarsitul liniei). Prima matrice reprezinta lungimea minima a drumurilor intre fiecare pereche de intersectii. A doua matrice reprezinta numarul maxim de strazi pe care se poate merge pentru a obtine distanta minima intre oricare pereche de noduri. Al j-ulea numar de pe a i-a linie reprezinta, pentru fiecare dintre cele doua matrici, raspunsul pentru perechea (i, j) de intersectii.
Restrictii si precizari
- 1 ≤ N ≤ 256
- Lungimea unui drum de la o intersectie la ea insasi va fi mereu 0
- 1 ≤ lungimea unui drum ≤ 100.000
rf.in | rf.out |
---|---|
5 0 2 3 4 5 2 0 4 5 1 3 4 0 1 2 4 5 1 0 3 5 1 2 3 0 | 0 2 3 4 3 2 0 3 4 1 3 3 0 1 2 4 4 1 0 3 3 1 2 3 0 0 1 1 2 2 1 0 2 3 1 1 2 0 1 1 2 3 1 0 2 2 1 1 2 0 |
3 0 9 100000 9 0 2 100000 2 0 | 0 9 11 9 0 2 11 2 0 0 1 2 1 0 1 2 1 0 |