| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 64 | 45 | 42 | 73.684% |
중앙대학교의 자랑스러운 청룡 푸앙이는 자신만의 별을 가지고 있다. $N$개의 정점과 $\frac{N(N-1)}{2}$개의 간선으로 이루어진 별은 무방향 완전 그래프이기 때문에 아름다운 모양을 띤다. 푸앙이는 지난번 명진이가 별의 간선을 잘라버리는 수모를 겪었기 때문에 이번에는 다른 별을 가져왔다. 이번에 가져온 별은 두 정점 $u$와 $v$를 연결하는 간선의 길이가 두 정점 번호의 곱인 $u\times v$이다.
푸앙이는 간선을 이용하여 그 간선이 잇는 두 정점을 이동할 수 있다. 푸앙이는 별 위의 $1$번 정점에서 $N$번 정점에 도착하는 여행을 떠나려고 한다. 그리고 그 사이에 $1$번 정점과 $N$번 정점이 아닌 서로 다른 $K$개의 정점을 한 번씩 방문해야 한다.
푸앙이가 별 위에서 여행할 수 있는 경로 중 이용한 간선의 길이 합이 최소가 되는 경로의 길이 합을 출력하라.
첫 번째 줄에 정점의 개수 $N$과 방문해야 하는 중간 정점의 개수 $K$가 공백으로 구분되어 주어진다. $(3 \le N \le 1\,000\,000$; $0 \le K \le N-2)$
첫 번째 줄에 $1$번 정점에서 시작하여 $K$개의 정점을 거쳐 $N$번 정점에 도착하는 경로 중 간선의 길이 합이 가장 작은 경로의 길이 합을 출력한다.
10 5
86
5 0
5
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2026 중앙대학교 프로그래밍 경진대회 (CPC) D1번