Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-05-06 21:46:02.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:risc.in, risc.outSursăAlgoritmiada 2010, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Risc

Bianca este agent secret la agentia BBB. Ea are o harta cu N obiective strategice, unite intre ele prin M drumuri bidirectionale fiecare cu o anumita lungime Li. Pentru fiecare obiectiv Bianca stie gradul de risc Ri al acelui obiectiv (cu cat e mai mare gradul de risc cu atat sunt mai mari sansele ca Bianca sa fie prinsa si incarcerata). Acum Bianca incearca sa execute planul urmatoarei misiuni. Ea isi pune Q intrebari de genul: care este drumul minim intre obiectivele Xi si Yi astfel incat orice nod intermediar prin care trec are riscul cel mult RMi? Ajutati-o pe Bianca sa isi indeplineasca misiunea cu succes.

Date de intrare

Fişierul de intrare risc.in va contine pe prima linie trei numere naturale N, M si Q, separate prin cate un spatiu, avand semnificatiile din enunt. Urmatoarea linie contine N numere, al i-lea dintre acesta fiind Ri, riscul obiectului i. Urmatoarele M linii contin fiecate cate trei numere Xi, Yi si Li reprezentand faptul ca intre obiectivele Xi si Yi exista un drum bidirectional de lungime Li. Urmatoarele Q linii contin cate trei numere Xi, Yi si RMi reprezentand cate o intrebare a Biancai.

Date de ieşire

În fişierul de ieşire risc.out veti afisa Q linii. Pe linia i veti afisa raspunsul la a i-a intrebare a Biancai, reprezentand distanta minima intre obiectivele Xi si Yi astfel incat orice nod intermediar de pe drumul dintre aceste noduri sa nu aibe riscul mai mare decat RMi, sau -1 in caz ca nu exista un astfel de drum.

Restricţii

  • 1 ≤ N ≤ 300
  • 1 ≤ M ≤ N2
  • 1 ≤ Q ≤ 100 000
  • Atentie: Pentru o intrebare Xi, Yi, RMi, doar obiectivele intermediare trebuie sa aibe riscul cel mult egal cu RMi

Exemplu

risc.inrisc.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?