Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dist3.in, dist3.out | Sursă | ad-hoc |
| Autor | Adăugată de |  CCEX2015 •CCEX2015 | |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 100000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dist3
Fie N puncte în planul bidimensional. Costul deplasării între două puncte P(x1, y1) şi Q(x2, y2) este definit prin expresia min(|x1 - x2|, |y1 - y2|). Se cere să se găseasca costul minim al unui drum care începe în punctul 1 şi se termină în punctul N.
Date de intrare
Fişierul de intrare dist3.in va conţine pe prima sa linie numărul N, reprezentând numărul de puncte. Urmează N linii, fiecare conţinând câte o pereche de numere întregi (X[i], Y[i]), reprezentând coordonatele punctelor.
Date de ieşire
În fişierul de ieşire dist3.out va conţine pe unica sa linie răspunsul cerut, costul minim al unui drum care începe în punctul 1 şi se termină în punctul N.
Restricţii
- 1 ≤ N ≤ 200.000
- 0 ≤ X[i], Y[i] ≤ 109
Exemplu
table(example). |_. dist3.in |_. dist3.out |
|
| 4
0 0
6 1
5 5
6 6
|
1
Explicaţie
Ruta 1 -> 2 -> 4 are costul 1 + 0 = 1.
