Fişierul intrare/ieşire:trafic.in, trafic.outSursă.campion 2005
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.075 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trafic

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

  • 3 ≤ N ≤ 154
  • 3 ≤ M ≤ 5054
  • 1 ≤ lungimea unei sosele ≤ 1023
  • 3 ≤ G ≤ 4095

Exemplu

trafic.intrafic.out
6 6 2
1 2 1
2 3 2
3 6 1
1 4 1
4 5 3
5 6 1
2.5

Explicatie

Se plaseaza un soldat in mijlocul drumului dintre 4 si 5 si un soldat pe drumul dintre 2 si 3 la 0.5 distanta de orasul 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content