Minimum Arborescence Total Cost

Problem

Find the minimum total weight of a spanning arborescence rooted at root.

Enumerate every assignment of one incoming edge to each non-root node, keep the assignments where following parent pointers from every node reaches the root without a cycle, and return the smallest total weight. edges is a list of directed [u, v, w] triples; n is small. Return -1 when no arborescence exists.

Hint

Every arborescence corresponds to exactly one choice of incoming edge per non-root node.

Test cases

case 1

in: [3,[[0,1,2],[1,2,1],[0,2,5]],0]

expected: 3

case 2

in: [3,[[0,1,3],[0,2,4],[1,2,1],[2,1,1]],0]

expected: 4

case 3

in: [3,[[0,1,1],[1,0,1]],0]

expected: -1

case 4

in: [1,[],0]

expected: 0

case 5

in: [4,[[0,1,1],[1,2,1],[2,3,1],[0,3,10]],0]

expected: 3

Starter codePython

def min_arborescence_cost(n, edges, root):
    # Your code here
    pass

5 test cases · run your code against them in the editor