Блог пользователя luciocf

Автор luciocf, 5 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится