Dandu-se drumul minim intr-un graf, sa se gaseasca un graf.

[•xoSauce]

Salutari tuturor,

Am tot cautat pe internet zilele astea pe infoarena,topcoder,codeforces si aparent nu pot gasi nimic despre aceasta problema:
Problema asta a aparut in destul de multe concursuri (o varianta destul de apropiata, chiar si la ICPC nwerc 2013).

Detaliile problemei:
Dandu-se matricea de drumuri minime al unui graf orientat, sa se gaseasca un graf care sa satisfaca matricea respectiva. Graful nu contine self-loops sau multi-edges. Daca nu se poate sa se afiseze -1, in caz contrar sa se afiseze matricea de adiacenta a grafului.
(restrictiile de care sunt interesat sunt n<=300, desi am vazut o varianta a problemei cu n mult mai mare)

Ex:
INPUT:
3
0 1 2
1 0 3
2 3 0

OUTPUT:
0 1 2
1 0 4
2 5 0

Din cate m-am gandit eu, ar trebui sa incerc sa fac un minimum spanning tree, pentru ca edge-urile respective garantat vor fi in graf, insa cum merg mai departe ? (nu sunt 100% sigur daca este corect ce am spus mai sus)

Multumesc si mult respect !

[•Impaler_009]

Pai nu cumva matricea de drumuri minime care iti este data poate constitui o matrice de adiacenta pentru graful initial ? In cazul asta, solutia n-ar exista decat atunci cand matricea de drumuri minime nu este corecta (se poate imbunatatii un drum folosindu-le pe celelalte), lucru ce poate fi verificat printr-un Roy-Floyd. Este problema http://www.infoarena.ro/problema/rfinv

[•xoSauce]

In problema de care vorbesc eu, nu iti este dat graful.

Si cat despre a il construi, nu sunt sigur, oarecum aici este problema mea.

Iti este data doar matricea de costuri. Nu sunt sigur daca problema asta ma poate ajuta in ceea ce caut, dar voi incerca. Nu stiam de problema. Multumesc.
___________________________________________________________________________

Last Edit:
Ah, interpretasem gresit ceea ce mi-ai spus tu. Acum am inteles. Voi incerca asa . Multumesc

[•xoSauce]

Pai nu cumva matricea de drumuri minime care iti este data poate constitui o matrice de adiacenta pentru graful initial ? In cazul asta, solutia n-ar exista decat atunci cand matricea de drumuri minime nu este corecta (se poate imbunatatii un drum folosindu-le pe celelalte), lucru ce poate fi verificat printr-un Roy-Floyd. Este problema http://www.infoarena.ro/problema/rfinv

Revin pentru a spune ca solutia propusa de Mihai a functionat ! Iti multumesc mult Mihai !