### kickbust13's blog

By kickbust13, history, 3 years ago,

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.

• 0

 » 3 years ago, # |   +3 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)
•  » » 3 years ago, # ^ |   0 Greg. thanks for the solution. Can you please elaborate the process of adding an edge in the graph. And is it possible to have a dp solution??
•  » » 12 months ago, # ^ |   0 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] ??
•  » » » 10 months ago, # ^ |   0 Because you can skip at most $k$ edges. It's unnecessary for positive weights, but for negative weights can result in wrong answers.
•  » » 5 months ago, # ^ |   0 Did anyone here implement his method? If yes, can you post the implementation?
 » 20 months ago, # |   0 can someone give link to problem of this type on codeforces
•  » » 16 months ago, # ^ |   0 Not on codeforces but there is one on Hackerearth. https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/shortest-path-revisited-9e1091ea/description/
•  » » 10 months ago, # ^ |   0 Here is one from codeforces.
 » 10 months ago, # |   0 Can someone please provide a detailed solution please....
•  » » 9 months ago, # ^ |   0
 » 9 months ago, # |   0 CODE with explanation void findMinDistance(vector> adj[], int N, int k) { // {dist, {node, leftout}} priority_queue>> pq; pq.push({0, {1, 0}}); int dist[N + 1][k + 1]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) { if (i == 0) dp[i][j] = 0; else dp[i][j] = INT_MAX; } } while (!pq.empty()) { // it -> {dist, {node, leftout}} auto it = pq.top(); pq.pop(); int node = it.second.first; int x = it.second.second; int dis = dist[node][x]; // it.first // iterate over all adjacent nodes for (auto iter : adj[node]) { int y = iter.first; int d = iter.secoond; // at first lets do without leaving out any edges if (dis + d < dist[y][x]) { dist[y][x] = dis + d; // pq is max heap, but i need minimal distance at top // so to make sure the max heap is used as // min heap, i converted it by having negatives, so // that max heap works in opposite pq.push({-1 * (dis + d), {y, x}}); // why did i take -1 ? } // if the max turn off edges have been done, // no need to further turn off edges if (x == k) continue; if (dis < dist[y][x + 1]) { dist[y][x + 1] = dis; // pq is max heap, but i need minimal distance at top // so to make sure the max heap is used as // min heap, i converted it by having negatives, so // that max heap works in opposite pq.push({-1 * (dis), {y, x + 1}}); // why did i take -1 ? } } } int mini = INT_MAX; // in reaching N, you can take any dist // by turning of 0, 1, 2, 3, 4, 5,... edges for (int i = 0; i <= k; i++) mini = min(mini, dist[N][i]); return mini;}
 » 9 months ago, # |   0 I think in this problem we can sort and get first M -K smallest edges and if M — K is small we can using Dijkstra (M — K) times
 » 8 months ago, # |   0 Can be solved with simple modification in djikstra #include using namespace std; #define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define F first #define S second #define pb push_back #define mp make_pair #define rep(i,a,b) for(int i=a;i vi; typedef pair pi; const int mod = 1e9 + 7; const long long INF = 1e18L + 5; const int mxn = 3e5 + 2; int cnt = 1; void solve() { int n,m,k,u,v,w,x,y; cin>>n>>m>>k; vector>>g(n+1); rep(i,0,m) { cin>>x>>y>>w; g[x].pb({y,w}); g[y].pb({x,w}); } int dp[n+1][k+1]; rep(i,1,n+1) rep(j,0,k+1) dp[i][j] = INT_MAX; for(int i = 0;i<=k;i++) dp[1][i] = 0; priority_queue,vector>,greater>>q; q.push({0,0,1}); while(!q.empty()) { arraya = q.top(); q.pop(); for(auto &p : g[a[2]]) { int u = p[0]; int w = p[1]; if(dp[u][a[1]] > dp[a[2]][a[1]] + w) { dp[u][a[1]] = dp[a[2]][a[1]] + w; q.push({ dp[u][a[1]] , a[1] , u}); } if(a[1] < k && dp[u][a[1]+1] > dp[a[2]][a[1]]) { dp[u][a[1]+1] = dp[a[2]][a[1]]; q.push({dp[u][a[1]+1] , a[1]+1,u}); } } } vectorans(n+1); for(int i = 1;i<=n;i++) { ans[i] = INT_MAX; for(int j = 0;j<=k;j++) { ans[i] = min(dp[i][j],ans[i]); } } rep(i,1,n+1) { cout<>t; while(t--) { solve(); cnt++; } return 0; } 
•  » » 6 months ago, # ^ |   0 Whts the expected time complexity?