페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2513

[중등부] 2025 KOI 1차대회 대비 모의고사 (6주차)

삼(3) 그래프
서브태스크
1초 1024MB

문제

정점(Node)은 개별 데이터를 담고 있는 그래프(Graph)의 기본 단위이며, 간선(Edge)은 두 정점 간의 연결 관계를 나타내는 그래프 구성 요소이다.

연결 그래프는 그래프 내의 모든 노드가 간선을 통해 서로 적어도 하나의 경로로 이어져 있어, 임의의 두 노드 간에 항상 도달 가능한 그래프를 말한다.

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

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

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

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

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


입력

첫 줄에 두 정수 N과 M이 주어진다. (3 \le N \le 100,000, 2 \le M \le 500,000)

이어 M줄에 걸쳐 세 정수 u, v, c가 주어지며, 이는 노드 u와 노드 v를 연결하기 위하여 c 비용이 필요하다는 의미이다.

  • 1 \le u, v \le N

  • u \ne v

  • 1 \le c \le 5 \cdot 10^5

  • 동일한 u, v쌍은 주어지지 않는다.

  • 최소 세 개의 노드로 구성된 연결 부분 그래프를 만들 수 있음이 보장된다.


출력

첫 줄에 최소 세 개의 노드로 구성된 연결 부분 그래프(subgraph)를 만드는 최소 비용을 출력한다.


부분문제

번호 점수 조건
#15점

N=3

#210점

N \le 20

#315점

N \le 300

#420점

M \le 1000

#520점

각 노드마다 연결할 수 있는 다른 노드의 수가 최대 2개이다.

#630점

추가 제약 조건 없음


예제 #1

5 7
1 2 1
4 5 2
2 3 3
3 4 4
2 5 5
1 5 6
5 3 7
4

예제 #2

38 57
1 2 570000
2 3 560000
3 4 550000
4 5 540000
5 6 530000
6 7 520000
7 8 510000
8 9 500000
9 10 490000
10 11 480000
11 12 470000
12 13 460000
13 14 450000
14 15 440000
15 16 430000
16 17 420000
17 18 410000
18 19 400000
1 19 390000
9 20 380000
21 20 370000
21 10 360000
22 23 350000
22 24 340000
23 2 330000
17 24 320000
7 25 310000
25 26 3400000
5 26 390000
26 9 380000
10 27 370000
27 14 360000
27 28 450000
28 12 440000
5 29 460000
29 30 420000
29 4 440000
30 20 440000
29 31 490000
31 20 480000
20 37 470000
37 3 460000
14 32 450000
32 33 440000
33 21 430000
21 34 420000
32 34 410000
32 15 400000
20 35 490000
36 21 480000
35 36 470000
35 22 460000
22 36 500000
16 38 400000
38 21 300000
37 23 400000
38 24 400000
660000

와일드캣(wildcat)을 닮은 입력이다.

로그인해야 코드를 작성할 수 있어요.