시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 4 | 3 | 3 | 75.000% |
In this problem, we will consider weighted undirected graphs where all edges have positive weights.
Let $D(G,i,j)$ be the length of the shortest path in graph $G$ between vertex $i$ and vertex $j$.
We are given a complete weighted undirected graph $G$ which consists of $n$ vertices numbered from $1$ to $n$. Among the spanning trees of $G$, the MDSST (Minimum Distance Sum Spanning Tree) is such $T$ for which the value $S(T) = \sum_{1 \leq i < j \leq n} D(T,i,j)$ is minimum. Your task is to find MDSST of $G$ and print $S(T)$.
The first line contains an integer $n$, the number of vertices in the graph ($2 \le n \le 15$). The $i$-th of the following $n-1$ lines contains $n-i$ integers separated by spaces. The $j$-th integer of this the line is the length of the edge between vertex $i$ and vertex $i+j$.
All the lengths are between $1$ and $10^9$, inclusive.
On the first line, print one integer: the value $S(T)$ for the MDSST you found.
4 3 2 1 5 6 7
18