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

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?

Auto comment: topic has been updated by SaddisticDude (previous revision, new revision, compare).What are the bounds? Are the bounds large enough to make the problem's answer not fit in integer?

Provide properly understandable statement

I couldn't find any problem in your solution either :(

Maybe seeing the test case can give some hint. (I don't have leetcode premium so I can't check that out myself)

For people having no leetcode premium: Question Link

Edit1: Just a suggestion when your code is long you can use spoiler tag to hide it.

Check under Markdown general formatting: https://codeforces.com/blog/entry/104522