### 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.  Comments (14)
 » 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)
•  » » 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??
•  » » 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.
•  » » Did anyone here implement his method? If yes, can you post the implementation?
 » can someone give link to problem of this type on codeforces
•  » » 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/
•  » » Here is one from codeforces.
 » 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;}
 » 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[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]) { int u = p; int w = p; if(dp[u][a] > dp[a][a] + w) { dp[u][a] = dp[a][a] + w; q.push({ dp[u][a] , a , u}); } if(a < k && dp[u][a+1] > dp[a][a]) { dp[u][a+1] = dp[a][a]; q.push({dp[u][a+1] , a+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; }