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
  • 1 ≤ Li ≤ 100 000
  • 1 ≤ Ri, RMi ≤ 100 000
  • Pentru 50% din teste N ≤ 100
  • Atentie: Pentru o intrebare Xi, Yi, RMi, doar obiectivele intermediare trebuie sa aibe riscul cel mult egal cu RMi
  • Doua obiective pot fi unite prin mai multe drumuri
  • Drumul minim de la un obiectiv la el insusi are distanta 0

Exemplu

risc.inrisc.out
5 6 6
5 4 3 2 1
1 2 1
2 3 1
3 4 5
4 1 3
4 5 10
5 2 2
3 1 1
3 1 2
3 1 4
4 2 1
4 2 3
4 2 5
-1
8
2
12
6
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content