can anyone help in solving the following question.
consider a weighted undirected graph. There is a source S and destination D and a value K. Find the length of the shortest path such that you can make at most K edges 0.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | orzdevinwang | 3844 |
3 | jqdai0815 | 3682 |
4 | jiangly | 3618 |
5 | Benq | 3529 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3443 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | atcoder_official | 162 |
3 | maomao90 | 162 |
5 | adamant | 158 |
5 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
can anyone help in solving the following question.
consider a weighted undirected graph. There is a source S and destination D and a value K. Find the length of the shortest path such that you can make at most K edges 0.
Name |
---|
We can create a graph with $$$k$$$ layers — lets call it $$$G[n][k]$$$. For each edge $$$(v,u,w)$$$ we add two types of edges to our graph:
$$$G[v][i]$$$ — $$$G[u][i]$$$ with weight $$$w$$$ (standard edge, needs to be in each layer)
$$$G[v][i]$$$ — $$$G[u][i+1]$$$ with weight $$$0$$$ ("skipping" edge, also in each layer)
Now if we calculate minimum distances to each vertex in the whole graph, distance to $$$G[v][l]$$$ will mean minimum distance to vertex $$$v$$$ if we made exactly $$$l$$$ edges to be equal 0.
If the weights are positive we can use Dijkstra's algorithm to calculate minimum distances giving us $$$O(nk*log(nk))$$$ complexity.
If weights can be negative we use Bellman–Ford algorithm giving us $$$O(n^2k^2)$$$ comlpexity.
Note that we need to take minimum distance to $$$d$$$ in all layers in order to find the answer (we "skip" at most $$$k$$$ edges)
Why we need to take minimum in all layers , should n't the minimum should be when you have skipped k edges . i.e G[dest][k] ??
Because you can skip at most $$$k$$$ edges. It's unnecessary for positive weights, but for negative weights can result in wrong answers.
can someone give link to problem of this type on codeforces
Here is one from codeforces.
CODE with explanation void findMinDistance(vector<pair<int, int>> adj[], int N, int k) { // {dist, {node, leftout}} priority_queue<pair<int, pair<int, int>>> pq; pq.push({0, {1, 0}});
}