Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | viteza2.in, viteza2.out | Sursă | Algoritmiada 2012, Runda finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Viteza2
"Speedy" Mirel just bought himself a new IA-mobile(a new generation car) and wants to take it to a ride through Targu Mures. The city is formed of M bidirectional streets and N intersections, each street connecting 2 different intersections. Having lots of free time he wants for each pair of cities (i, j) to find the shortest path to intersection j starting from intersection i and going only through streets in the city. Unfortunately for him(and for you) he insists that on each street through which he passes to reach a higher speed than what he has reached on the previous one.
On every intersection he has to brake(so his speed drops to 0) and the longer the street is the higher the speed he can reach on it.
Unfortunately Mirel isn't good at other things besides driving so he asks for your help in determining for each pair of intersections (i, j) how fast can he go from intersection i to intersection j reaching on each street passed a higher speed than on the previous one.
Knowing N, M and the M streets find out for Mirel the shortest path between each 2 intersections under his restrictions.
Input Data
The input file viteza2.in contains on the first line 2 numers N and M reprezenting the number of intersections and the number of streets in the city.
The next M lines each contain 3 numbers A, B and D which describe a street of distance D in the city connecting intersections A and B.
Output Data
In the output file viteza2.out there should be exactly N lines each containing N numbers.
The j-th number on the i-th line must represent the shortest path from intersection i to intersection j respecting Mirel's restrictions. If there is no such path you must print -1 instead.
Restrictions
- 1 ≤ N ≤ 1.000
- 1 ≤ M ≤ 5.000
- 1 ≤ A, B, ≤ N
- 1 ≤ D ≤ 1.000.000
- For each 2 intersections A and B there is maximum one street connecting them
- Any 2 street have different lengths
- For 20% of the tests 1 ≤ N ≤ 15 si 1 ≤ M ≤ 50
- For another 20% of the tests 1 ≤ N ≤ 100 si 1 ≤ M ≤ 1000
Example
| viteza2.in | viteza2.out |
|---|---|
| 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 |
Observations
From intersection 2 to intersection 4 there is also a path of length 4(2 -> 1 -> 4) but it does not respect Mirel's restrictions(the length of the street from 1 to 4 is smaller than the length of the street from 2 to 1)
