== include(page="template/taskheader" task_id="rfinv") ==
Poveste si cerinta...
Probabil ati auzit cu totii de algoritmul Roy-Floyd. Acest algoritm determina distantele minime intre oricare doua noduri ale unui graf neorientat, avand costuri pozitive pe muchii. Dandu-se un graf neorientat conex, de pe muchiile caruia s-au sters costurile, precum si rezultatul aplicarii algoritmului Roy-Floyd pe acest graf (inainte de stergerea costurilor de pe muchii), trebuie sa determinati daca se pot asocia costuri tuturor muchiilor grafului astfel incat sa se obtina rezultatul dat.
h2. Date de intrare
...
Prima linie a fisierului de intrare $rfinv.in$ contine numarul intreg $T$, reprezentand numarul de teste. In continuare, urmeaza cele $T$ teste. Fiecare test are urmatoare structura. Prima linie a fiecarui test contine $2$ numere intregi $N$ si $M$, reprezentand numarul de noduri si numarul de muchii din graf. Urmatoarele $M$ linii contin cate $2$ numere intregi diferite $a$ si $b$, avand semnificatia ca exista o muchie intre nodurile numerotate cu $a$ si $b$. Urmatoarele $N$ linii contin cate $N$ numere intregi, reprezentand rezultatul algoritmului Roy-Floyd. A $i$-a linie dintre aceste $N$ linii contine distantele minime dintre nodul $i$ si fiecare din cele $N$ noduri ale grafului.
h2. Date de iesire
...
Pentru fiecare test afisati in fisierul de iesire $rfinv.out$ cate o linie continand sirul $"DA"$, daca este posibil sa se asocieze costuri muchiilor grafului astfel incat rezultatul algoritmului Roy-Floyd sa fie cel precizat, sau sirul $"NU"$, in caz contrar.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 30$
* $1 ≤ N ≤ 50$
* $0 ≤ M ≤ N*(N-1)/2$
* Fie $dmin(i,j)$ distanta minima dintre nodurile $i$ si $j$, rezultata prin aplicarea algoritmului Roy-Floyd. Se garanteaza ca $dmin(i,i)=0$ si $dmin(i,j)=dmin(j,i)$.
* Distantele minime intre oricare $2$ noduri diferite sunt numere intregi din intervalul $[1,10000]$.
h2. Exemplu
table(example). |_. rfinv.in |_. rfinv.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2
3 2
1 2
3 2
0 5 10
5 0 4
10 4 0
2 1
1 2
0 13
13 0
|NU
DA
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="rfinv") ==
