MDSST 계산하기

이 문제에서는 모든 간선의 가중치가 양수인 가중 무방향 그래프를 다룬다.

$D(G,i,j)$를 그래프 $G$에서 정점 $i$와 정점 $j$ 사이 최단 경로의 길이로 정의하자.

정점 $1$부터 $n$까지 번호가 붙은 $n$개의 정점으로 이루어진 완전 가중 무방향 그래프 $G$가 주어진다. $G$의 신장 트리 중에서 MDSST(Minimum Distance Sum Spanning Tree)는 $S(T) = \sum\_{1 \leq i < j \leq n} D(T,i,j)$ 값을 최소로 하는 트리 $T$이다. $G$의 MDSST를 찾아 $S(T)$를 출력하시오.

첫째 줄에는 정점의 수 $n$이 주어진다 ($2 \le n \le 15$). 다음 $n-1$개의 줄 중 $i$번째 줄에는 $n-i$개의 정수가 공백으로 구분되어 주어진다. 이 줄의 $j$번째 정수는 정점 $i$와 정점 $i+j$ 사이 간선의 길이이다.

모든 길이는 $1$ 이상 $10^9$ 이하이다.

첫째 줄에 찾은 MDSST의 $S(T)$ 값을 정수로 출력한다.