Fişierul intrare/ieşire:galerie.in, galerie.outSursă.com 2009, Runda 1
AutorSerban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.7 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Galerie

Cârtiţele din toată ţara se vor aduna în săptămânile următoare în oraşul Văgăuna, cu ocazia "Meeting-ului Anual al Cârtiţelor". Participanţii au fost cazaţi la hotel Subpământ în N camere. Camerele sunt aşezate pe un coridor în ordine de la 1 la N. Cum cârtiţele sunt animale înclinate spre socializare, organizatorii iau în calcul derularea a M vizite. Mai exact, se stie ca dintr-o camera P vor pleca C cartiţe spre altă camera Q. Pentru ca cele C cârtiţe sa ajunga în camera Q ele trebuie sa treacă prin toate camerele ce despart P de Q. Timpul petrecut pe drum se va calcula astfel: |P-Q|*C. Organizatorii sunt conştienţi de faptul ca membrii meeting-ului pot pierde foarte multă vreme cu vizitele, şi astfel îşi pun T întrebări de tipul: dacă am construi o galerie de la camera X la camera Y, care ar fi parcursă de fiecare cârtiţă într-un timp K, cu cât s-ar îmbunătăţi suma timpilor necesari pentru derularea celor M vizite?

Cerinţă

Ajutaţi-i pe organizatori să răspundă la cele T întrebări.

Date de intrare

Pe prima linie a fişierului de intrare galerie.in se vor afla trei numere naturale N,M si T cu semnificaţia din enunţ. Următoarele M linii vor conţine câte trei numere naturale P,Q,C descriind faptul ca C cârtiţe pleacă din camera P spre camera Q. Pe fiecare din următoarele T linii se vor găsi cate trei numere X,Y,K descriind câte o întrebare a organizatorilor.

Date de ieşire

Fişierul de ieşire galerie.out va conţine T linii, pe fiecare linie câte un număr Di, reprezentând raspunsul la a i-a întrebare pusă de organizatori.

Restricţii

  • 1 ≤ T ≤ 250 000
  • 1 ≤ N, M ≤ 100 000
  • 1 ≤ P, Q, X, Y, K ≤ N
  • P ≠ Q, X ≠ Y
  • 0 ≤ C ≤ 50
  • Pentru 20% din teste se garantează T,M ≤ 1 000
  • Dintr-o camera nu vor pleca în vizite mai multe cârtiţe decât au fost cazate
  • Cârtiţele vor parcurge camerele în sens strict crescător sau strict descrescător
  • Dintr-o cameră P din care nu porneşte o galerie, cârtiţele se pot deplasa doar în camera P-1 sau P+1
  • Cârtiţele nu sunt obligate să folosească galeriile

Exemplu

galerie.ingalerie.out
4 1 1
1 4 2
1 3 1
2

Explicaţie

Dacă nu este construită vreo galerie cârtiţele urmează traseul 1-2,2-3,3-4, şi ajung în timp total 2*3=6. În cazul primei întrebări, traseul ales va fi 1-3,3-4, fiind parcurs în timp 4. Timpul final se îmbunataţeşte cu 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content