alirezaopmc's blog

By alirezaopmc, history, 3 years ago, In English

There is a directed weighted graph with $$$m$$$ edges. There are $$$n$$$ edges marked as good one. Suppose that a vertex $$$h$$$ is called root and we want to find a minimum path starting from $$$h$$$ ending to itself that contains at least $$$k$$$ good edges. Path definition in this problem is as regular path that can not consists of same edges except good one. In fact on this path we can visit good edges as many times we want but not for other edges. (And also note that this path should end with $$$h$$$ itself.)

There is no constraints. I just wanna to know how to beat this problem theoretically.

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