==Include(page="template/taskheader" task_id="rf")==

==Include(page="template/raw")==
 
Link: [1]File-List
 
Roy-Floyd

h2. 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.
h2. Date de intrare

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.
 
h2. 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$.

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.

h2. Date de iesire

h2. Date de Iesire
 
 
 
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.

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.

h2. 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
 
 
 
table(example). |. rf.in| rf.out|
 
 
5 0 2 3 4 3
 
0 2 3 4 5 2 0 3 4 1
 
2 0 4 5 1 3 3 0 1 2
 
3 4 0 1 2 4 4 1 0 3
 
4 5 1 0 3 3 1 2 3 0
 
5 1 2 3 0 0 1 1 2 2
 

* $1 ≤ N ≤ 256$
* Lungimea unui drum de la o intersectie la ea insasi va fi mereu $0$
* $1 ≤ lungimea unui drum ≤ 100.000$
 
table(example). |_. 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
 
 
 
rf.in rf.out
 
 
3 0 9 11
 
0 9 100000 9 0 2
 
9 0 2 11 2 0
 
100000 2 0 0 1 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 |

2 1 0
 
 
 
 
 
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/rf/enunt_files/filelist.xml

==Include(page="template/taskfooter" task_id="rf")==

1325