| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 1 | maomao90 | 161 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | atcoder_official | 149 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 10 | cry | 143 |
Hello everyone,
I have some trouble with a problem and I hope someone may help me to solve it:
Given a graph N vertices and M edges (N <= 50, M <= N * (N — 1) / 2). Each edge has a weight w (w <= 1e4). And the task is to find if there is a path with the total weight exactly equals to S (S <= 1e18).
Thanks in advance!
(EDITED)
because DFS doesn't enumerate all paths. This task is simply NP-complete.
What I thought so far:
If S is sufficiently large, the path must contain a cycle. So the final path will be comprised of several simple paths connecting cycles, and each cycle/simple path will be used some number of times. I couldn't advance more, but for me, it looks more like a math/ dp problem in some sense, than a graph problem. I hope that can be of help!
Bump. Btw, I think I know how to do it in N^4W, but it's not sufficient I presume (assuming edges are undirected, for directed case I have no idea actually).
May I ask how to solve in $$$O(n^4W)$$$?
Not entirely sure if it works but:
Let's look at the last edge you traversed, suppose it's weight is C. Then you were in second-to-last vertex with (S — C) traversed, in particular you visited this vertex when (lenght of path so far) MOD (C) == (S — C) MOD (C). So it's sufficient to find FIRST such moment, that you were able to locate yourself at second-to-last vertex with (lenght of path so far) MOD (C) == (S — C) MOD (C) (since then you can traverse this edge with length back and forth). To do this we iterate over an edge which is candidate for being this last edge with weight C. We can find first moment to locate at (vertex, rem MOD C) by just running dijkstra on graph where nodes are (vertex, rem MOD C). So final complexity would be M * MW (assuming we implement Dijkstra running in E + VlogV).
Eh, I have already thought about your solution, but I think your complexity may be still large (at least N * N * W * log). The timelimit is 2s.