정점(Node)은 개별 데이터를 담고 있는 그래프(Graph)의 기본 단위이며, 간선(Edge)은 두 정점 간의 연결 관계를 나타내는 그래프 구성 요소이다.
연결 그래프는 그래프 내의 모든 노드가 간선을 통해 서로 적어도 하나의 경로로 이어져 있어, 임의의 두 노드 간에 항상 도달 가능한 그래프를 말한다.

N개의 노드가 각각 독립적으로 존재하고 있으며, 현재는 어떤 간선도 연결되어 있지 않다.

일부 노드 쌍 사이에는 간선을 추가할 수 있으며, 각 간선을 추가하는 데는 일정한 비용이 든다.

이러한 간선들은 아직 그래프에 포함되지 않은 상태이며, 필요 시 선택적으로 추가할 수 있다.

그래프 이론을 좋아하는 정올이는, 이 노드들 중 최소 세 개 이상을 선택하여 하나의 연결 그래프(connected subgraph)를 만들고자 한다.

정올이를 위해, 최소 세 개의 노드로 구성된 연결 부분 그래프(subgraph)를 만들기 위해 지불해야 하는 간선들의 최소 총 비용을 구하시오.

#8426 upload 807 done 181 how_to_reg 105 call_split Subtask

삼(3) 그래프 timer 1s memory 1024MB

#8426
Subtask

삼(3) 그래프 1s 1024MB