Pintant cases P70058


Statement
 

pdf   zip

thehtml

En un carrer hi ha n cases. La façana de cada casa i es pot pintar amb tres colors diferents, amb costs respectius c1i, c2i i c3i. Calculeu el cost mínim de pintar totes les cases, amb una restricció: les cases adjacents han de tenir colors diferents.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguida de c11, c12, …, c1n, seguits de c21, c22, …, c2n, seguits de c31, c32, …, c3n. Suposeu 1 ≤ n ≤ 105, i que tots els costs es troben entre 0 i 109.

Sortida

Per a cada cas, escriviu el cost mínim de pintar les n façanes.

Public test cases

  • Input

    1
20
10
30

5
900000000 800000000 900000000 800000000 900000000
800000000 900000000 800000000 900000000 800000000
1000000000 1000000000 0 1000000000 1000000000

3
0 1 0
42 1000 10
23 1000 6

    Output

    10
3200000000
30
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++