I appeared for Flipkart coding test day before yesterday and got stuck on this problem:<br>↵
You are given an undirected weighted graph with n vertices and m edges. In one move you can make any edge weight zero. You can perform atmost K moves. You have to tell what is the shortest path from a starting node A to an ending node B after performing atmost K moves.<br>↵
1<=n<=1000<br>↵
0<=K<n<br>↵
1<=m<=10000<br>↵
1<=w<=10^9 (weight of edge) <br>↵
Can anybody please tell me how to approach this problem?<br>↵
I found this problem on [quora](https://www.quora.com/Given-an-N-vertex-weighted-graph-if-we-can-change-the-weight-of-K-of-the-edges-to-zero-what-is-the-shortest-path-from-1-to-N) also but couldn't understand the approach clearly.<br>↵
<b> [UPD]: </b> This problem has been solved thanks to ExplodingFreeze and _dobby_<br>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h> ↵
#include <ext/pb_ds/assoc_container.hpp> ↵
using namespace std;↵
using namespace __gnu_pbds;↵
// Policy based data structure ↵
typedef tree<int, null_type, ↵
less_equal<int>, rb_tree_tag, ↵
tree_order_statistics_node_update> ↵
indexed_set; ↵
#define ll long long int↵
#define pii pair<ll,ll>↵
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))↵
#define vi vector<ll>↵
#define vii vector<pii>↵
#define all(x) x.begin(),x.end()↵
#define eb emplace_back↵
#define yes cout<<"YES"<<endl; return;↵
#define no cout<<"NO"<<endl; return;↵
#define flus fflush(stdin); fflush(stdout);↵
#define F first↵
#define S second↵
#define np next_permutation↵
#define inf 1e18↵
#define mod 1000000007↵
#define N 1005↵
#define pi (double)2*acos(0.0)↵
#define minpq priority_queue <ll, vector<ll>, greater<ll>>↵
#define maxpq priority_queue<ll> ↵
/*******************************************************************/↵
struct state{↵
ll dist,node,used;↵
state(ll dist1,ll node1,ll used1){↵
dist=dist1;↵
node=node1;↵
used=used1;↵
}↵
bool operator<(const state&s) const{↵
if(this->dist==s.dist){↵
if(this->node==s.node){↵
return this->used < s.used;↵
} else{↵
return this->node < s.node;↵
}↵
} else{↵
return this->dist < s.dist;↵
}↵
}↵
};↵
ll n,m,a,b,k;↵
vii adj[N];↵
ll dist[N][N];↵
void solve(){↵
cin>>n>>m>>a>>b>>k;↵
rep(i,0,m){↵
ll u,v,w;↵
cin>>u>>v>>w;↵
adj[u].eb(v,w);↵
adj[v].eb(u,w);↵
}↵
rep(i,0,n+1){↵
rep(j,0,k+1){↵
dist[i][j]=inf;↵
}↵
}↵
rep(i,0,k+1){↵
dist[a][i]=0;↵
}↵
map<pii,pii> pa;↵
set<state> s;↵
s.insert(state(0,a,0));↵
while(!s.empty()){↵
state curr=*s.begin();↵
// curr.print();↵
s.erase(s.begin());↵
for(auto ch:adj[curr.node]){↵
if(dist[ch.F][curr.used]>dist[curr.node][curr.used] + ch.S){↵
state temp(dist[ch.F][curr.used],ch.F,curr.used);↵
auto it=s.find(temp);↵
if(it!=s.end())↵
s.erase(it);↵
dist[ch.F][curr.used]=dist[curr.node][curr.used] + ch.S;↵
pa[{ch.F,curr.used}]={curr.node,curr.used};↵
temp.dist=dist[ch.F][curr.used];↵
s.insert(temp);↵
}↵
if(curr.used+1<=k and dist[ch.F][curr.used+1]>dist[curr.node][curr.used]){↵
state temp(dist[ch.F][curr.used+1],ch.F,curr.used+1);↵
auto it=s.find(temp);↵
if(it!=s.end())↵
s.erase(it);↵
dist[ch.F][curr.used+1]=dist[curr.node][curr.used];↵
pa[{ch.F,curr.used+1}]={curr.node,curr.used};↵
temp.dist=dist[ch.F][curr.used+1];↵
s.insert(temp);↵
}↵
}↵
}↵
ll ans=inf;↵
rep(i,0,k+1){↵
ans=min(ans,dist[b][i]);↵
}↵
if(ans>=inf){↵
cout<<-1<<endl;↵
} else{↵
cout<<ans<<endl;↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
// cin>>t;↵
t=1;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
You are given an undirected weighted graph with n vertices and m edges. In one move you can make any edge weight zero. You can perform atmost K moves. You have to tell what is the shortest path from a starting node A to an ending node B after performing atmost K moves.<br>↵
1<=n<=1000<br>↵
0<=K<n<br>↵
1<=m<=10000<br>↵
1<=w<=10^9 (weight of edge) <br>↵
Can anybody please tell me how to approach this problem?<br>↵
I found this problem on [quora](https://www.quora.com/Given-an-N-vertex-weighted-graph-if-we-can-change-the-weight-of-K-of-the-edges-to-zero-what-is-the-shortest-path-from-1-to-N) also but couldn't understand the approach clearly.<br>↵
<b> [UPD]: </b> This problem has been solved thanks to ExplodingFreeze and _dobby_<br>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h> ↵
#include <ext/pb_ds/assoc_container.hpp> ↵
using namespace std;↵
using namespace __gnu_pbds;↵
// Policy based data structure ↵
typedef tree<int, null_type, ↵
less_equal<int>, rb_tree_tag, ↵
tree_order_statistics_node_update> ↵
indexed_set; ↵
#define ll long long int↵
#define pii pair<ll,ll>↵
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))↵
#define vi vector<ll>↵
#define vii vector<pii>↵
#define all(x) x.begin(),x.end()↵
#define eb emplace_back↵
#define yes cout<<"YES"<<endl; return;↵
#define no cout<<"NO"<<endl; return;↵
#define flus fflush(stdin); fflush(stdout);↵
#define F first↵
#define S second↵
#define np next_permutation↵
#define inf 1e18↵
#define mod 1000000007↵
#define N 1005↵
#define pi (double)2*acos(0.0)↵
#define minpq priority_queue <ll, vector<ll>, greater<ll>>↵
#define maxpq priority_queue<ll> ↵
/*******************************************************************/↵
struct state{↵
ll dist,node,used;↵
state(ll dist1,ll node1,ll used1){↵
dist=dist1;↵
node=node1;↵
used=used1;↵
}↵
bool operator<(const state&s) const{↵
if(this->dist==s.dist){↵
if(this->node==s.node){↵
return this->used < s.used;↵
} else{↵
return this->node < s.node;↵
}↵
} else{↵
return this->dist < s.dist;↵
}↵
}↵
};↵
ll n,m,a,b,k;↵
vii adj[N];↵
ll dist[N][N];↵
void solve(){↵
cin>>n>>m>>a>>b>>k;↵
rep(i,0,m){↵
ll u,v,w;↵
cin>>u>>v>>w;↵
adj[u].eb(v,w);↵
adj[v].eb(u,w);↵
}↵
rep(i,0,n+1){↵
rep(j,0,k+1){↵
dist[i][j]=inf;↵
}↵
}↵
rep(i,0,k+1){↵
dist[a][i]=0;↵
}↵
map<pii,pii> pa;↵
set<state> s;↵
s.insert(state(0,a,0));↵
while(!s.empty()){↵
state curr=*s.begin();↵
// curr.print();↵
s.erase(s.begin());↵
for(auto ch:adj[curr.node]){↵
if(dist[ch.F][curr.used]>dist[curr.node][curr.used] + ch.S){↵
state temp(dist[ch.F][curr.used],ch.F,curr.used);↵
auto it=s.find(temp);↵
if(it!=s.end())↵
s.erase(it);↵
dist[ch.F][curr.used]=dist[curr.node][curr.used] + ch.S;↵
pa[{ch.F,curr.used}]={curr.node,curr.used};↵
temp.dist=dist[ch.F][curr.used];↵
s.insert(temp);↵
}↵
if(curr.used+1<=k and dist[ch.F][curr.used+1]>dist[curr.node][curr.used]){↵
state temp(dist[ch.F][curr.used+1],ch.F,curr.used+1);↵
auto it=s.find(temp);↵
if(it!=s.end())↵
s.erase(it);↵
dist[ch.F][curr.used+1]=dist[curr.node][curr.used];↵
pa[{ch.F,curr.used+1}]={curr.node,curr.used};↵
temp.dist=dist[ch.F][curr.used+1];↵
s.insert(temp);↵
}↵
}↵
}↵
ll ans=inf;↵
rep(i,0,k+1){↵
ans=min(ans,dist[b][i]);↵
}↵
if(ans>=inf){↵
cout<<-1<<endl;↵
} else{↵
cout<<ans<<endl;↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
// cin>>t;↵
t=1;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
