there are 'n' nodes and 'm' edges in a graph. each node may or may not contain certain number of a item. all nodes have same item but different number of that item.
we have to go from source to destination in minimum time collecting 'k' number of this item. each edge is weighted,weights may or may not be same. there are no self loops. edges are bidirectional.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 5 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Let's all nodes have exactly one item, 'k' = 'n', weight of each edge exactly 1, source and destination is the same node. Then, collecting 'k' items in minimum time = 'n' means to find the Hamiltonian cycle for Hamiltonian graphs. So this is NP-hard problem.
I think it's pretty simple to make a dp solution in 2^n * n^2. Like dp[mask][x][y] = minimum time to collect x item, visit nodes stored in 'mask' and ended in node 'y'.
why dijikstra with dp[node][k] , will not work ?