Hi I came across this problem which I later found exactly on leetcode,↵
↵
A series of highways connect n cities numbered from 0 to n — 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli.↵
↵
You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the ith highway for a cost of tolli / 2 (integer division). Each discount may only be used once, and you can only use at most one discount per highway.↵
↵
Return the minimum total cost to go from city 0 to city n — 1, or -1 if it is not possible to go from city 0 to city n — 1↵
↵
You can find more explanation here [here](https://leetcode.com/problems/minimum-cost-to-reach-city-with-discounts/)↵
↵
I know this can be solved by using Djikstra but I was curious whether it can be solved using dfs + memoization(top down DP) ↵
↵
Tried to implement a solution but its failing on 72/76 test case. ↵
↵
↵
~~~~~↵
class Solution {↵
public:↵
const int inf = 1e9;↵
vector<vector<pair<int,int>>> adj;↵
vector<vector<int>>dp;↵
vector<bool>vis;↵
int n;↵
int dfs(int u, int discounts){↵
if(u==n-1)↵
return 0;↵
↵
if(dp[u][discounts]!=-1){↵
return dp[u][discounts]; ↵
}↵
↵
vis[u] = true;↵
↵
int ans = inf;↵
for(auto& [v, w]:adj[u]){↵
if(vis[v])↵
continue;↵
ans = min(ans, w + dfs(v, discounts));↵
if(discounts>0){↵
ans = min(ans, (w/2) + dfs(v, discounts-1));↵
}↵
}↵
vis[u] = false;↵
return dp[u][discounts] = ans;↵
}↵
int minimumCost(int nn, vector<vector<int>>& highways, int discounts) {↵
n = nn;↵
adj.resize(n);↵
dp.assign(n, vector<int>(discounts+1, -1));↵
vis.assign(n, false);↵
↵
for(auto& edges:highways){↵
auto [u,v,w] = tuple(edges[0], edges[1], edges[2]);↵
adj[u].push_back({v,w});↵
adj[v].push_back({u,w});↵
}↵
↵
int ans = dfs(0, discounts);↵
↵
if(ans<inf)↵
return ans;↵
return -1;↵
}↵
};↵
~~~~~↵
↵
↵
↵
Can anyone help to understand the flaw in my solution or propose their own solution?
↵
A series of highways connect n cities numbered from 0 to n — 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli.↵
↵
You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the ith highway for a cost of tolli / 2 (integer division). Each discount may only be used once, and you can only use at most one discount per highway.↵
↵
Return the minimum total cost to go from city 0 to city n — 1, or -1 if it is not possible to go from city 0 to city n — 1↵
↵
You can find more explanation here [here](https://leetcode.com/problems/minimum-cost-to-reach-city-with-discounts/)↵
↵
I know this can be solved by using Djikstra but I was curious whether it can be solved using dfs + memoization(top down DP) ↵
↵
Tried to implement a solution but its failing on 72/76 test case. ↵
↵
↵
~~~~~↵
class Solution {↵
public:↵
const int inf = 1e9;↵
vector<vector<pair<int,int>>> adj;↵
vector<vector<int>>dp;↵
vector<bool>vis;↵
int n;↵
int dfs(int u, int discounts){↵
if(u==n-1)↵
return 0;↵
↵
if(dp[u][discounts]!=-1){↵
return dp[u][discounts]; ↵
}↵
↵
vis[u] = true;↵
↵
int ans = inf;↵
for(auto& [v, w]:adj[u]){↵
if(vis[v])↵
continue;↵
ans = min(ans, w + dfs(v, discounts));↵
if(discounts>0){↵
ans = min(ans, (w/2) + dfs(v, discounts-1));↵
}↵
}↵
vis[u] = false;↵
return dp[u][discounts] = ans;↵
}↵
int minimumCost(int nn, vector<vector<int>>& highways, int discounts) {↵
n = nn;↵
adj.resize(n);↵
dp.assign(n, vector<int>(discounts+1, -1));↵
vis.assign(n, false);↵
↵
for(auto& edges:highways){↵
auto [u,v,w] = tuple(edges[0], edges[1], edges[2]);↵
adj[u].push_back({v,w});↵
adj[v].push_back({u,w});↵
}↵
↵
int ans = dfs(0, discounts);↵
↵
if(ans<inf)↵
return ans;↵
return -1;↵
}↵
};↵
~~~~~↵
↵
↵
↵
Can anyone help to understand the flaw in my solution or propose their own solution?
