Cost màxim d'un camí (2) P70102


Statement
 

pdf   zip

thehtml

Donat un graf dirigit i complet amb n vèrtexos, calculeu el cost màxim de tots els camins amb els vèrtexos en ordre creixent. El graf ve representat amb una matriu M de mida n × n, on per a tot parell (i, j) amb i ≠ j, mij és el cost (potser negatiu) de l’arc que va de i a j.

Per exemple, el cost màxim del primer test és 100, corresponent al camí 0 → 1 → 3 → 4, el qual té cost 20 − 10 + 90 = 100.

Entrada

L’entrada consisteix en el nombre de vèrtexos n, seguit de la matriu M (n línies, cadascuna amb n enters), Els vèrtexos es numeren de 0 a n−1. Podeu suposar 1 ≤ n ≤ 103, que la diagonal només té zeros, i que tots els altres nombres estan entre −106 i 106.

Sortida

Escriviu el cost màxim de tots els camins amb els vèrtexos en ordre creixent.

Public test cases

  • Input

    6
 0  20   5  -3  80  -2
11   0  30 -10 -12   3
22 -10   0 -50  15  -5
23 -60  35   0  90   7
97  14 -70 -11   0 -11
 1   2   3   4   5   0

    Output

    100

  • Input

    1
0

    Output

    0

  • Input

    3
 0 -6  8
-4  0  9
-7 -2  0

    Output

    9
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++