| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
Given a directed graph, source node and destination node you have to start from source with value 1 and reach destination node along some path where each edge has a multiple associated with it. Find the maximum value you can attain? Assume, if cycles exists it does not increases value to greater than 1.
Can we use Dijkstra's algorithm here or a quadratic dp+dfs is more appropriate?
Dijkstra won't work for this problem.
Can you please elaborate?
Auto comment: topic has been updated by DarkSilver (previous revision, new revision, compare).
multiple of what, exactly?
So each edge has a value associated and if you travel through that edge the “multiple” is multiplied to get the new value.
Okay. So you're saying that we start with value = 1 at the source destination and every time we go through that edge, value = value * multiplier of edge. We need to get to destination with as big a value as possible. And what is that about the cycles even? Like, you're not allowed to go through a cycle?
You could go through cycles but let's assume the value is always less than 1 when you traverse a cycle ensuring that you do not run into infinite loops.
Write it a little better please. Multiple of what exactly? Can you give the original problem statement maybe?
Taking the logarithm of each value will make your problem identical to the single source longest path problem. Following the analysis of such a problem, a Dijkstra's algorithm works if and only if your original graph doesn't contain edges with a value (or multiple as you stated it) more than 1, which would correspond to a positive weight on the transformed graph.
I don't get your 'quadratic dp+dfs' though, for it seems that it only works on DAGs. On more general graphs one might suggest using Bellman-Ford to solve this problem.
That is a sound approach, thank you!