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

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 \times n$, on per a tot parell $(i, j)$ amb $i \ne j$, $m_{ij}$ é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 \to 0 \to 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 \le n \le 11$, $0 \le x < n$, que la diagonal només té zeros, i que tots els altres nombres estan entre $-10^6$ i $10^6$.

Sortida

Escriviu el cost màxim de tots els camins sense vèrtexos repetits que surten de $x$.