본문 바로가기

알고리즘

항구 도시 보급망

New Era · 3번Lv. 3최소 신장 트리

항구 도시 보급망

문제 설명

라이캣이 떠나 있는 동안 대리인 No.1은 세계 곳곳에 항구 도시를 세우고, 나라마다 특산품 생선을 잡게 해 촘촘한 유통망을 만들었습니다. 위니브 월드의 배는 마법으로 날아다니기 때문에, 항로만 열려 있으면 날씨와 상관없이 오갈 수 있습니다.

이제 그 유통망이 혁명군의 보급망이 됩니다. 어느 항구 도시에서 보낸 물자든 다른 모든 항구 도시에 닿아야 합니다. 바로 잇는 항로가 없어도 다른 도시를 거쳐 갈 수 있으면 됩니다.

"교역하던 항로는 그대로 쓰고, 모자란 곳만 새로 열면 된다냥. 돈은 한 노드도 허투루 쓰지 않는다냥!"

항구 도시는 1번부터 n번까지 있습니다. 이미 열려 있는 항로는 비용 없이 쓸 수 있고, 새로 열 수 있는 항로마다 여는 비용이 정해져 있습니다. 비용 단위인 '노드'는 위니브 월드의 돈 단위로, 그래프의 노드(점)와는 다른 말입니다. 모든 항로는 양쪽 방향으로 오갈 수 있습니다.

도시 수 n, 새로 열 수 있는 항로 목록 routes, 이미 열려 있는 항로 목록 existing이 주어질 때, 모든 항구 도시가 서로 오갈 수 있도록 새 항로를 여는 최소 비용을 구하세요. 새 항로를 모두 열어도 이어지지 않는 도시가 있으면 -1을 반환하세요.


제한 사항

  • 입력은 [n, routes, existing] 형태입니다.
  • 1 ≤ n ≤ 1,000
  • 0 ≤ routes의 길이 ≤ 10,000. 원소 [a, b, cost]는 a번 도시와 b번 도시를 잇는 항로를 cost 노드에 열 수 있다는 뜻입니다.
  • 0 ≤ existing의 길이 ≤ 1,000. 원소 [a, b]는 a번 도시와 b번 도시를 잇는 항로가 이미 열려 있다는 뜻입니다.
  • 1 ≤ a, b ≤ n, a ≠ b, 1 ≤ cost ≤ 100,000 (모두 정수)
  • 같은 두 도시를 잇는 항로가 여러 번 나올 수 있습니다(비용이 다를 수 있음).
  • 도시가 1개뿐이면 답은 0입니다.

입출력 예

입력출력
[4, [[1, 2, 5], [2, 3, 1], [3, 4, 2], [1, 4, 7], [1, 3, 3]], []]6
[5, [[1, 2, 10], [2, 3, 4], [3, 4, 8], [4, 5, 3], [1, 5, 6]], [[1, 2], [3, 4]]]7
[4, [[1, 2, 3]], [[3, 4]]]-1

입출력 설명

첫 번째 예

열려 있는 항로가 없습니다. 2-3(1노드), 3-4(2노드), 1-3(3노드)을 열면 네 도시가 모두 이어지고 비용은 6노드입니다. 이보다 싸게 모두 잇는 방법은 없습니다.

두 번째 예

1-2, 3-4 항로가 이미 열려 있습니다. 4-5(3노드)를 열면 3·4·5번 도시가 이어지고, 2-3(4노드)을 열면 모든 도시가 이어집니다. 비용은 7노드입니다.

세 번째 예

1-2 항로를 열어도 1·2번 도시와 3·4번 도시를 잇는 항로가 없으므로 -1을 반환합니다.

예시 테스트

#입력기대값
1[4, [[1, 2, 5], [2, 3, 1], [3, 4, 2], [1, 4, 7], [1, 3, 3]], []]6
2[5, [[1, 2, 10], [2, 3, 4], [3, 4, 8], [4, 5, 3], [1, 5, 6]], [[1, 2], [3, 4]]]7
3[4, [[1, 2, 3]], [[3, 4]]]-1

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 13개도 함께 채점해요.