### kickbust13's blog

By kickbust13, history, 4 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 (8)
| Write comment?
 » 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.
•  » » Did anyone here implement his method? If yes, can you post the implementation?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   #include using namespace std; // https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i,s,e) for(int i=s ; i < e ; i++) #define rrep(i,s,e) for(int i=s ; i > e ; i--) #define srep(i,s,e,j) for(int i=s ; i < e ; i+=j) #define tr(i,x) for(auto i : x) #define vinp(a) for(int i=0 ; i>a[i] #define ainp(a,n) for(int i=0; i>a[i] #define int long long #define vi vector #define vvi vector> #define vs vector #define vb vector #define vpi vector #define maxpqi priority_queue #define minpqi priority_queue , greater > #define mem0(x) memset(x, 0, sizeof(x)) #define mem1(x) memset(x, -1, sizeof(x)) #define pii pair #define F first #define S second #define mk make_pair #define pb push_back #define pf push_front #define endl '\n' #define gcd(a,b) __gcd(a,b) #define clr(x) memset(x,0,sizeof(x)) #define lb lower_bound #define ub upper_bound #define npos string::npos #define all(x) x.begin(),x.end() #define sayyes cout << "YES" << endl #define sayno cout << "NO" << endl struct Node{ int v, k, d; Node(){ v = k = d = 0; } Node(int _v, int _k, int _d){ v = _v,k = _k,d = _d; } }; typedef struct Node Node; class Compare{ public: bool operator()(const Node& a, const Node& b){ // min priority queue according to dist return a.d > b.d; } }; vectoradj; vvi dp; int n, K; void dijkstra(int src){ dp[src] = 0; // distance from src to src after using 0 coupon is 0 priority_queue, Compare>pq; pq.push(Node(src, 0, 0)); Node tp; int from, k, dist; int to, edgew; while(!pq.empty()){ tp = pq.top(); pq.pop(); from = tp.v, k = tp.k, dist = tp.d; if(dp[from][k] < dist) continue; for(auto p: adj[from]){ to = p.F, edgew = p.S; if(dist + edgew < dp[to][k]){ dp[to][k] = dist + edgew; pq.push(Node(to, k, dp[to][k])); } if(k+1 <= K && dist < dp[to][k+1]){ dp[to][k+1] = dist; pq.push(Node(to, k+1, dp[to][k+1])); } } } } void solve(){ int m; cin >> n >> m >> K; // K = 1; // max number of edges on which discount can be used. adj.assign(n+1, vpi()); int u, v, w; rep(i, 0, m){ cin >> u >> v >> w; adj[u].pb({v, w}); } dp.assign(n+1, vi(K+1, LONG_MAX)); // dp[i][k] denote minimum distance from 1 to i after using discount coupon on k edges dijkstra(1); int ans = LONG_MAX; rep(j, 0, K) ans = min(ans, dp[n][j]); cout << ans << endl; } int32_t main(){ fastio // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int tt = 1; // cin >> tt; while(tt--){ solve(); // cout << solve() << endl; // cout << (solve() ? "yes" : "no") << endl; } return 0; } 
 » can someone give link to problem of this type on codeforces
•  » » 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;}