== include(page="template/taskheader" task_id="cezar") ==
In Roma antica exista {$N$} asezari senatoriale distincte, cate una pentru fiecare dintre cei $N$ senatori ai Republicii. Asezarile senatoriale sunt numerotate de la $1$ la $N$, intre oricare doua asezari existand legaturi directe sau indirecte. O legatura este directa daca ea nu mai trece prin alte asezari senatoriale intermediare. Edilii au pavat unele dintre legaturile directe dintre doua asezari (numind o astfel de legatura pavata "strada"), astfel incat intre oricare doua asezari senatoriale sa existe o singura succesiune de strazi prin care se poate ajunge de la o asezare senatoriala la cealalta.

Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste $1$ ban pentru ca a fost transportat cu lectica pe acea strada.

Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste 1 ban pentru ca a fost transportat cu lectica pe acea strada.

La alegerea sa ca prim consul, Cezar a promis ca va dota Roma cu o lectica gratuita care sa circule pe un numar de $K$ strazi ale Romei astfel incat orice senator care va circula pe strazile respective, sa poata folosi lectica gratuita fara a plati. Strazile pe care se deplaseaza lectica gratuita trebuie sa fie legate intre ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).
In plus, Cezar a promis sa stabileasca sediul salii de sedinte a Senatului intr-una dintre asezarile senatoriale aflate pe traseul lecticii gratuite. Problema este de a alege cele $K$ strazi si amplasarea sediului salii de sedinte a Senatului astfel incat, prin folosirea transportului gratuit, senatorii, in drumul lor spre sala de sedinte, sa faca economii cat mai insemnate. In calculul costului total de transport, pentru toti senatorii, Cezar a considerat ca fiecare senator va calatori exact o data de la asezarea sa pana la sala de sedinte a Senatului.