luciocf's blog

By luciocf, 5 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +25
  • Vote: I do not like it