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

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 \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 100, corresponent al camí $0 \to 1 \to 3 \to 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 \le n \le 10^3$, 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 amb els vèrtexos en ordre creixent.