SaddisticDude's blog

By SaddisticDude, history, 5 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SaddisticDude (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the bounds? Are the bounds large enough to make the problem's answer not fit in integer?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Provide properly understandable statement

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.cc/blog/entry/104522