Fişierul intrare/ieşire:distante.in, distante.outSursăpreONI 2006 Runda 1
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Distante

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 D1 D2 ... DN 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.

Restrictii

  • 0 ≤ T ≤ 10
  • 1 ≤ a,b,S ≤ N ≤ 50.000
  • 0 ≤ M ≤ 100.000
  • 0 ≤ c ≤ 1.000

Exemplu

distante.indistante.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content