 # Weekend Planning - Sprinklr hiring challenge

This question was asked in Sprinklr hiring challenge.

You are given a road network with N cities and M bidirectional roads. Each road has some positive amount of tax associated to it, meaning if there is a road connecting cities A and B with tax C, you need to pay C rupees to the government every time you use this road.

But you have a wildcard which can be used at most K times and when you use this wildcard while using using this road, you do not need to pay tax associated with that road. You are planning to visit one city this weekend, due to the limited budget you want to estimate minimum possible cost from your home city to every other city, so that you can choose the destination according to your budget. Your home city is a city numbered 1.

INPUT FORMAT

The first line of the input contains N, M, and K following M lines containing 3 integers U, V and C, meaning there is a road between cities U and V with tax C associated.

OUTPUT FORMAT

Print N space separated integers in a single line, ith integer indicating the minimum cost of travelling from city 1 to j

CONSTRAINTS

1 <= N,M <= 5 * 10^5

0 <= K <= 15

SAMPLE INPUT

4 4 1

1 2 2

2 3 3

1 3 6

3 4 11

SAMPLE OUTPUT

0 0 0 5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {

``````ll t=1;
//cin>>t;
while(t--)
{
ll n,m,k;
cin>>n>>m>>k;
vector<ll>v[n+1];
ll i,j;
unordered_map<ll,unordered_map<ll,ll>>mp;
for(i=0;i<n;i++)
{
ll x,y,c;
cin>>x>>y>>c;
v[x].push_back(y);
v[y].push_back(x);
mp[x][y]=c;
mp[y][x]=c;
}

vector<vector<ll>>dist(k+1,vector<ll>(n+1,INT_MAX));
for(i=0;i<=k;i++)
dist[i]=0;

for(i=0;i<=k;i++)
{
list<pair<ll,ll>>l;
l.push_back({1,0});
while(!l.empty())
{
ll x=l.front().first;
ll lev=l.front().second;
l.pop_front();
ll temp=v[x].size();
for(j=0;j<temp;j++)
{
ll q=v[x][j];

if(i==0)
{
if(dist[i][q]>dist[i][x]+mp[x][q])
{
dist[i][q]=dist[i][x]+mp[x][q];
l.push_back({q,lev+1});
}
continue;
}

if(dist[i][q]!=0)
{
if(lev+1<=i)
{
dist[i][q]=0;
l.push_back({q,lev+1});

}
else{
ll temp=min(dist[i][x]+mp[x][q],dist[i-1][x]);
if(dist[i][q]>temp)
{
dist[i][q]=temp;
l.push_back({q,lev+1});
}
}

}

}

}
}
for(i=1;i<=n;i++)
cout<<dist[k][i]<<" ";

}
return 0;
``````

}

PLEASE CHECK ANYONE WHETHER IT IS CORRECT OR NOT, I HAVE USED DYNAMIC PROGRAMMING HERE
Time complexity O(K*(N+M))
dist[i][q] denotes minimum path sum till from 1 to q with i wildcards