Cost màxim d'un camí (1) P46634


Statement
 

pdf   zip

html

Donat un graf dirigit i complet amb n vèrtexos, i un vèrtex inicial x, calculeu el cost màxim de tots els camins sense vèrtexos repetits que surten de x. El graf ve representat amb una matriu M de mida n × n, on per a tot parell (i, j) amb ij, 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 80, corresponent al camí 1 → 0 → 3, el qual té cost −10 + 90 = 80.

Entrada

L’entrada consisteix en el nombre de vèrtexos n, seguit de la matriu M (n línies, cadascuna amb n enters), seguida del vèrtex inicial x. Els vèrtexos es numeren de 0 a n−1. Podeu suposar 1 ≤ n ≤ 11, 0 ≤ x < n, 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 sense vèrtexos repetits que surten de x.

Public test cases
  • Input

    4
      0 -10  30  90
    -10   0  50 -12
    -60  35   0  15
     14 -70 -11   0
    1
    

    Output

    80
    
  • Input

    1
    0
    0
    

    Output

    0
    
  • Input

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

    Output

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