Maximum cost of a path (2) P70102


Statement
 

pdf   zip

thehtml

Given a directed and complete graph with n vertices, compute the maximum cost of all the paths with the vertices in increasing order. The given graph is represented by an n × n matrix M, where for every pair (i, j) with ij, mij is the (perhaps negative) cost of the arc from i to j.

For instance, the maximum cost of the first test is 100, because of the path 0 → 1 → 3 → 4, with cost 20 − 10 + 90 = 100.

Input

Input consists of the number of vertices n, followed by the matrix M (n lines, each one with n integer numbers), followed by the initial vertex x. Vertices are numbered from 0 to n−1. You can assume 1 ≤ n ≤ 103, that the diagonal has only zeros, and that the rest of numbers are between −106 and 106.

Output

Print the maximum cost of all the paths with the vertices in increasing order.

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
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++