I've encountered this question several times, but I'm not very sure how to implement it.
Everywhere it discussess pseudo-code, like:
Can someone share code for this question as well, to help me understand it, I can't seem to find a good explanation for this as well:
I can understand a dp state dp[i][j] referring to ith edges where i've already skipped j edges 1<=i<=N, 0<=j<=k;
so is the transition for each state calculated while maintaining a priority queue:
this is what is guessed it must work like?
const int N = 1e5+5;
vector<int> G[N];
map<pair<int,int>,int> weight;
//implementation of n(log(n)) djikstra with priority queue
.
.
.
//cost caculation for each j
//what is initialisation of dp going to look like, all INF?
const int INF = 1e9;
vector<vector<int>> dp(N, vector<int> (k, INF));
for(auto a:dp[src]){
a = 0;
}
.
.
.
for( int skipedges = 0; skipedges <= k; skipedges++){
for( auto a: G[i])
// handing sceranrios where skipedges-1<0;
dp[i][skipedges] = min(dp[i][skipedges], dp[a][skipedges-1] , dp[a][skipedges] + weight[{i,a}] )
}
}any guidance would be helpful, thanks. and code for reference would be really helpful
PS: This is my first question, so apologies if you find this a little illstructured or unclear.