Lista de probleme 1

Etichete

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.

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ş?