Minimum Network Connection Cost

Choose undirected links so that every vertex can reach every other vertex, with minimum total cost. A link can be used in either direction. Return −1 if the available links cannot connect the whole network. You do not need to return the selected links.

Implement minimum_network_connection_cost(vertices, links).

Input

vertices: The number of network vertices.

links: Available links [u, v, cost].

Output

Return the minimum total cost, −1 if impossible, or 0 for a one-vertex network.

Ràng buộc

1 ≤ vertices ≤ 100,000. 0…200,000 links; endpoints are distinct vertices in 1…vertices. Costs are 1…1,000,000,000. Parallel links are allowed. The total fits signed 64-bit.

Ví dụ

Đầu vào:
links = [
    [1, 2, 4],
    [2, 3, 2],
    [1, 3, 7]
]
vertices = 3

Kết quả mong đợi:
expected = 6

Đầu vào:
std::vector<std::vector<long long>> links = {
    {1, 2, 4},
    {2, 3, 2},
    {1, 3, 7}
};
long long vertices = 3;

Kết quả mong đợi:
long long expected = 6;

Đầu vào:
long[][] links = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 2},
    new long[] {1, 3, 7}
};
long vertices = 3;

Kết quả mong đợi:
long expected = 6;

Đầu vào:
links = [
    [1, 2, 4]
]
vertices = 3

Kết quả mong đợi:
expected = -1

Đầu vào:
std::vector<std::vector<long long>> links = {
    {1, 2, 4}
};
long long vertices = 3;

Kết quả mong đợi:
long long expected = -1;

Đầu vào:
long[][] links = new long[][] {
    new long[] {1, 2, 4}
};
long vertices = 3;

Kết quả mong đợi:
long expected = -1;

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

• CSES: Road Reparation