### luciocf's blog

By luciocf, 4 months ago, ,

I was thinking about this problem for quite a while but couldn't solve it. The statement is the following:

Given an undirected and weighted simple graph with $N$ vertices and $M$ edges, find the cost (sum of weights in edges) of its shortest cycle, that is, the one with least cost. Repeated edges are not allowed in the cycle.

Note: It is assumed the graph has at least one cycle.

Constraints:

$1 \leq N \leq 10^4$, $1 \leq M \leq 10^5$

$0 \leq W_i \leq 100$, where $W_i$ is the weight of the ith edge.

The problem can be found here: https://dunjudge.me/analysis/problems/697/. Can anyone help me solve it?