Visiting at least k good edges — Graph Problem

Правка en1, от alirezaopmc, 2021-05-14 10:06:46

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.

Теги #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский alirezaopmc 2021-05-14 10:06:46 630 Initial revision (published)