trafic

Trafic

== include(page="template/taskheader" task_id="trafic") ==

Poveste si cerinta...

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.
 
h2. 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.

h2. 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$".

h2. 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$.

h2. Restrictii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. trafic.in |_. trafic.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 6 2
  1 2 1
  2 3 2
  3 6 1
  1 4 1
  4 5 3
  5 6 1
| 2.5

|
h3. 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$

== include(page="template/taskfooter" task_id="trafic") ==

1760