A research park has n labs 0 .. n-1. The contractor supplies a symmetric price matrix price:
price[i][j] is the cost of a direct link between labs i and j, or -1 if that link is impossible.
The diagonal is always 0.
Return the minimum total price of a set of links that connects every lab (directly or indirectly),
or -1 if that cannot be done.
Examples
Input: price = [[ 0, 4, 1,-1],
[ 4, 0, 2, 6],
[ 1, 2, 0, 3],
[-1, 6, 3, 0]]
Output: 6
Explanation: links 0-2 (1), 2-1 (2) and 2-3 (3).
Input: price = [[0, -1],
[-1, 0]]
Output: -1
Constraints
1 <= n <= 500,-1 <= price[i][j] <= 10**6- Target
O(n**2)time (the matrix is dense).
Goals
- Run Prim's algorithm directly on a dense cost matrix
- Keep the cheapest known link to the tree for every outside node
- Report when some lab can never be attached