Fişierul intrare/ieşire:portal3.in, portal3.outSursă.com 2011
AutorMihai GheorgheAdăugată decezar305Mr. Noname •cezar305
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Portal3

Derpina se afla intr-o matrice cu N+1 linii si M+1 coloane in elementul 0, 0. Ea vrea sa ajunga cat mai repede la prietenul ei Derp care se afla in matrice in elementul N, M. La fiecare pas Derpina se poate muta intr-o casuta invecinata. Ca sa ajunga mai rapede la prietenul ei, Derpina a apelat la firma de portale. Aceasta a construit 3 perechi de portale in matrice, P1 cu P2, P3 cu P4 si P5 cu P6. Fiecare portal Pi se afla in matrice la pozitia Xi, Yi. Pentru a folosi perechea de portale i, Derpina trebuia sa se afle in matrice intr-o casuta unde se afla un portal din perechea i si sa activeze portalul. Ea va ajunge instant in celalalt portal, dar timpul pentru activarea unui portal din perechea i este Ci. Derpinei ii place sa isi petreaca timpul in bucatarie si vrea sa stea cat mai putin timp in afara ei. Derpina va cere ajutorul si pentru asta trebuie sa calculati timpul minim in care ea ajunge la Derp.

Date de intrare

Fişierul de intrare portal3.in va contine pe prima linie un numar natural T reprezentand numarul de teste. Pentru fiecare test pe prima linie se afla N si M, pe a doua linie X1, Y1, X2, Y2, C1, pe a treia linie X3, Y3, X4, Y4, C2 si pe a patra linie X5, Y5, X6, Y6, C3.

Date de ieşire

Fişierul de ieşire portal3.out va contine T linii. Pe linia i se va afla raspunsul pentru testul i.

Restricţii

  • 1 ≤ T ≤ 10.000
  • 1 ≤ N, M ≤ 1.000.000.000
  • 0 ≤ X1, X2, X3, X4, X5, X6 ≤ N
  • 0 ≤ Y1, Y2, Y3, Y4, Y5, Y6 ≤ M
  • 0 ≤ C1, C2, C3 ≤ 1.000.000.000

Exemplu

portal3.inportal3.out
1
50 50
10 5 20 4 3
27 19 35 16 5
19 23 42 40 11		67
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content