Fişierul intrare/ieşire:tollroads.in, tollroads.outSursăad-hoc
AutorAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

TollRoads

N oraşe sunt conectate între ele prin M autostrăzi bidirecţionale, fiecare autostradă (a, b) având un cost de tranzit c ataşat. Se doreşte revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul şi necesită investigaţie, deoarece o parte dintre cele N oraşe sunt centre comerciale sau turistice importante.

Cerinţă

Se doreşte să se afle răspunsul la o serie de Q întrebări de forma: (X, T) - câte dintre celelalte N-1 oraşe, au acces către oraşul X, cu o taxă totală de cel mult T către fiecare oraş?

Date de intrare

Fişierul de intrare tollroads.in conţine pe primul rând numerele N, M şi Q reprezentând numărul de oraşe, numărul de autostrăzi şi numărul de interogări. Pe fiecare din următoarele M rânduri sunt scrise câte trei numere a, b, c, separate prin câte un spaţiu, reprezentând două oraşe între care există o autostradă şi costul autostrăzii. Pe următoarele Q rânduri se află scrise câte două numere X şi T, separate prin spaţiu, reprezentând datele interogărilor, conform enunţului.

Date de ieşire

În fişierul de ieşire tollroads.out se vor scrie pe fiecare dintre primele Q rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.

Restricţii

  • 1 ≤ N ≤ 10^5
  • 1 ≤ M ≤ 10^5
  • 1 ≤ a, b ≤ N
  • 1 ≤ c ≤ 10^5
  • 1 ≤ T ≤ 10^5
  • 1 ≤ Q ≤10^2
  • între orice două oraşe poate exista mai mult de o autostradă

Exemplu

tollroads.intollroads.out
7 8 5
1 2 1
2 3 2
2 4 4
3 5 1
4 5 1
5 6 2
1 6 5
6 7 1
1 6
1 5
1 4
2 3
4 4
6
5
3
3
5

Explicaţie

Oraşele 2,3,4,5,6,7 au acces către oraşul 1 cu taxă maximă 6
Oraşele 2,3,4,5,6 au acces către oraşul 1 cu taxă maximă 5
Oraşele 2,3,5 au acces către oraşul 1 cu taxă maximă 4
Oraşele 1,3,5 au acces către oraşul 2 cu taxă maximă 3
Oraşele 2,3,5,6,7 au acces către oraşul 4 cu taxă maximă 4

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?