BitCell

Va salut! Am intampinat de curand o problema la care nu ii gasesc raspunsul.Trag de mine de ceva vreme,dar tot nu reusesc sa conturez ceva.Dupa mai multe idei - nefinalizate,am ajuns la una - mai ,mai realizabila .

Ma gandeam sa formez matricea costurilor folosind Algoritmul Roy Floyd: pentru elementul A[i][j],cunoasteam costul minim de la nodul i la nodul j.Apoi formam toate lanturile posibile de la nodul i la j ( folosind cumva parcurgerea BFS ) si il alegeam pe cel de lungime maxima cu costul acesta minim. Problema e ca nu pot sa pun in aplicatie treaba cu toate lanturile, si mai e si vorba de ineficienta.
Voi ce ziceti ? Orice foarte mic indiciu/sau oricare alt raspuns va fi mai mult decat apreciat !

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

Fisierul de intrare: rf.in


Fisierul de iesire: rf.out


P.S : Problema e dupa Infoarena

EDIT:


In caz ca a interesat pe cineva problema,aflati ca dupa o zi de cofruntari,aflu ca una dintre solutii se afla,asa evident.. printre comentarii.Pacat,eram increzator ca pot ajunge si eu la solutie ( azi,maine,saptamana care vine ).

roymin e matricea costurilor: roymin[i][j]=x,unde x este costul minim de la nodul i la nodul j
roymax e matricea ce retine numarul maxim de drumuri de la nodul i : roymax[i][j]=x,unde x este numarul de drumuri maxim de la nodul i la nodul j