Dupa ce au impartit tara in
judete maimutele au o alta problema, trebuie sa opreasca traficul de banane. Tara
maimutelor are N
orase numerotate de la 1
la N legate intre ele prin
M sosele bidirectionale.
Intre oricare doua orase exista maxim o sosea, dar exista drum - direct sau prin
orase intermediare. Orasele 1
si N sunt capitale.
In ultima vreme intre cele doua capitale s-a intensificat traficul cu banane.
Pentru a combate traficul presedintele are la dispozitie G
soldati pe care poate sa-i aseze oriunde pe o sosea, oricat de aproape de un oras,
insa nu in oras. In cazul unui atac asupra uneia dintre capitale toti soldatii
trebuie sa ajunga in acea capitala. Soldatii se misca cu aceasi viteza constanta.Timpul
necesar unei astfel ce mobilizari este egal cu maximul distantelor de la soldati
la una dintre capitale.
Cerinta
Scrieti un program care sa
gaseasca o asezare a soldatilor astfel incat orice ruta de la o capitala la
alta sa treaca printr-o sosea cu cel putin un soldat si timpul de mobilizare
in cel mai rau caz sa fie minim.
Date de intrare
Pe prima linie a fisierului de intrare trafic.in sunt scrise trei numere
N M G separate prin cate
un singur spatiu.
Pe urmatoarele M linii
sunt scrise cate trei numere separate prin spatii a
b c cu semnificatia "exista sosea bidirectionala de la orasul a
la orasul b de lungime
c".
Date de iesire
Prima linie a fisierului
trafic.out va contine timpul minim
de mobilizare cu o zecimala exacta. Daca nu exista solutie se va scrie -1.
Restrictii
2 < N < 155
2 < M < 5055
0 < lungimea
unei sosele < 1024
2 < G < 4096
Exemplu
trafic.in
trafic.out
6 6 2
1 2 1
2 3 2
3 6 1
1 4 1
4 5 3
5 6 1
2.5
Fechete Dan Ionut Universitatea Bucuresti,
Facultatea de Matematica si Informatica mailto:f_dany@eminem.com