Fişierul intrare/ieşire:rfinv.in, rfinv.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.025 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rfinv

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.

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.

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.

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].

Exemplu

rfinv.inrfinv.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content