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)

can someone give link to problem of this type on codeforces

Can someone please provide a detailed solution please....

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}});

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;

}

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

Can be solved with simple modification in djikstra

#include<bits/stdc++.h>
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<b;i++)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> 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<vector<array<int,2>>>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<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>q;
    q.push({0,0,1});
    while(!q.empty())
    {
        array<int,3>a = 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});
            }
        }
    }
    vector<int>ans(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<<ans[i]<<" ";
    }
    cout<<"\n";

 
}
int main()
{
    //fastIO;
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
        cnt++;
    }
    return 0;
}