viteza2

Viteza2

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

Poveste şi cerinţă...

Vitezomanul Mirel tocmai si-a cumparat un nou IA-mobil(o masina de ultima generatie) si vrea sa se plimbe cu el prin Targu Mures. Orasul este format din $M$ strazi bidirectionale si $N$ intersectii, fiecare strada unind $2$ intersectii distince. Avand mult timp la dispozitie el vrea pentru fiecare pereche de intersectii $(i, j)$ sa ajunga cat mai repede in intersectia $j$ plecand din interectia $i$ si mergand doar pe strazile din oras. Din pacate pentru el (si pentru voi) vrea neaparat ca pe orice strada pe care merge sa prinda o viteza mai mare decat a prins pe strada anterioara.
In fiecare intersectie el trebuie sa franeze pentru a schimba strada, iar cu cat strada este mai lunga cu atat poate sa ajunga la o viteza mai mare pe ea.
Din pacate Mirel nu se pricepe la mai mult decat condus asa ca va roaga pe voi sa aflati pentru fiecare pereche de intersectii $(i, j)$ cat de repede poate sa ajunga din intersectia $i$ la intersectia $j$ atingand pe fiecare strada o viteza mai mare decat pe anterioara.
 
Stiind $N$, $M$ si cele $M$ strazi aflati pentru Mirel drumul cel mai scurt dintre $oricare 2$ intersectii respectand cerintele lui.

h2. Date de intrare

Fişierul de intrare $viteza2.in$ ...

Fişierul de intrare $viteza2.in$ contine pe prima linie $N$ si $M$ reprezentand numarul de intersectii si strazi din oras.
Urmatoarele $M$ linii contin fiecare $3$ numere $A$, $B$, si $D$ cu semnificatia ca intre intersectiile $A$ si $B$ exista o strada de lungime $D$ care le uneste.

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $viteza2.out$ ...

În fişierul de ieşire $viteza2.out$ trebuie sa se gaseasca $N$ linii fiecare cu cate $N$ numere.
Al $j$-lea numar de pe a $i$-a linie trebuie sa reprezinta lungimea minima a unui drum care pleaca din intersectia $i$, se termina in intersectia $j$ si respecta cerintele lui Mirel. Daca nu exista un drum ce respecta aceste cerinte Mirel va roaga sa afisati $-1$

h2. Restricţii

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

* $1 ≤ N ≤ 1.000$
* $1 ≤ M ≤ 5.000$
* $1 ≤ A, B, ≤ N$
* $1 ≤ D ≤ 1.000.000$
* $Pentru oricare doua intersectii A, B exista *maxim* o strada care le uneste$
* $Lungimile strazilor sunt *diferite* doua cate doua$
* $Pentru 20% din teste 1 ≤ N ≤ 15 si 1 ≤ M ≤ 50$
* $Pentru inca 20% din teste 1 ≤ N ≤ 100 si 1 ≤ M ≤ 1000$

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

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

| 4 4
1 4 1
1 2 3
2 3 7
3 4 8
| 0 3 9 1
3 0 7 15
-1 7 0 8
1 4 8 0

|

h3. Explicaţie

h3. Observatii

...

De la intersectia $2$ la intersectia $4$ exista un drum de lungime $4(2 -> 1 -> 4)$ insa nu respecta cerintele lui Mirel(mai exact lungimea muchiei de la $1 -> 4$ este mai mica decat cea a muchiei $2 -> 1$)

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

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