Teleport - MarisaOJ: Marisa Online Judge

Teleport

Time limit: 1000 ms
Memory limit: 256 MB
Given a connected weighted graph with $n$ vertices and $m$ edges, you are allowed to add an edge with weight 0 between any two vertices such that the total shortest path distances between all pairs of vertices is minimized. In other words, minimize: $$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} d(i,j) $$ where $d(i,j)$ is the shortest path distance between vertices $i$ and $j$. ### Input - The first line contains two integers $n$ and $m$. - The next $m$ lines each contain three integers $u$, $v$, and $w$, representing an edge between vertices $u$ and $v$ with weight $w$. ### Output - Print a single integer, the answer to the problem. ### Constraints - $1 \le n \le 100$ - $1 \le m \le \frac{n \times (n-1)}{2}$ - $1 \le u,v \le n$ - $1 \le w \le 10^4$ ### Example Input: ``` 4 5 1 2 3 1 3 6 2 3 4 2 4 7 3 4 2 ``` Output: ``` 14 ``` Explanation: Add an edge $(1,4)$ with weight $0$.