Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 23:27:37.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	distante.in, distante.out	Sursă	preONI 2006 Runda 1
Autor	Mircea Bogdan Pasoi	Adăugată de
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	2/5

Distante

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge `==Include(file="template/raw")==` cand esti multumit cu continutul paginii.

Un bun prieten de-al lui Zaharel, Bronzarel este la spital bolnav de tifos. Fiind buni prieteni, Zaharel se duce sa-l viziteze pe acesta. Ultima data cand a fost in vizita, Bronzarel desenase pe peretii spitalului mai multe grafuri neorientate conexe cu costuri (da, si Bronzarel este pasionat de informatica!) si mai mult de atat calculase pentru fiecare dintre acestea distantele minime de la un nod sursa ales la toate celelalte. Zaharel, curios ca intotdeana, a decis ca vrea sa vada daca Bronzarel delireaza sau nu si si-a notat pe o foaie de hartie ceea ce scrisese acesta pe pereti. Cand a ajuns acasa, el s-a decis sa vada pentru care din grafuri distantele minime calculate de Bronzarel erau corecte.

Cerinta

Scrieti un program care-l ajuta pe Zaharel sa determine pentru fiecare graf daca distantele minime au fost calculate correct.

Date de intare

Pe prima linie din fisierul de intrare distante.in se va gasi un numar T, reprezetand cate grafuri sunt pe foaie. Urmatoarele linii vor descrie succesiv cate un graf. Prima linie din descrierea unui graf va contine numerele N, M, si S reprezentand numarul de noduri , numarul de muchii si, respectiv, nodul sursa de la care se calculeaza distantele minime. A doua linie din descriere contine N elemente D₁ D₂ ... D_N reprezentand distantele minime calculate de Bronzarel. Urmatoarele M linii vor contine cate trei numere naturale a b c reprezentand faptul ca exista o muchie de cost c de la a la b.

Date de Iesire

Fisierul de iesire distante.out va contine T linii, fiecare cu cate un cuvant: DA daca distantele minime au fost calculate correct pentru graful respective, sau NU altfel.