Worst path P10051


Statement
 

pdf   zip

html

Given a directed and complete graph with n vertices, and an initial vertex x, compute the maximum cost of all the paths without repeated vertices that begin at x. 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 80, corresponding to the path 1 → 0 → 3, with cost −10 + 90 = 80.

Input

Input consists of several cases, each one with 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 ≤ 18, 0 ≤ x < n, that the diagonal has only zeros, and that the rest of numbers are between −106 and 106.

Output

For every case, print the cost of the worst path without repeated vertices that begins at x.

Public test cases
  • Input

    4
      0 -10  30  90
    -10   0  50 -12
    -60  35   0  15
     14 -70 -11   0
    1
    
    1
    0
    0
    
    3
     0  6  8
    -4  0  3
    -7 -2  0
    2
    

    Output

    80
    0
    0
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Dotzè Concurs de Programació de la UPC - Final
    Date
    2014-10-01