== include(page="template/taskheader" task_id="distante") ==
==Include(page="template/taskheader" task_id="distante")==
Poveste ...
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.
h2. Cerinta
...
Scrieti un program care-l ajuta pe Zaharel sa determine pentru fiecare graf daca distantele minime au fost calculate correct.
h2. Restrictii
h2. 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{~1~} D{~2~} ... 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$}.
h2. Date de intrare
h2. 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.
h2. Date de iesire
h2. Restrictii
...
* $0 ≤ T ≤ 10$
* $1 ≤ a,b,S ≤ N ≤ 50.000$
* $0 ≤ M ≤ 100.000$
* $0 ≤ c ≤ 1.000$
h2. Exemplu
| distante.in | distante.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="distante") ==
table(example). |_. distante.in |_. distante.out |
| 2
5 6 1
0 1 7 3 6
1 2 1
1 3 7
1 4 3
3 4 4
2 5 5
4 5 6
4 4 2
1 0 2 3
1 2 1
2 3 1
2 4 1
3 4 1
| DA
NU |
==Include(page="template/taskfooter" task_id="distante")==
