No Dijkstra | DFS | C++ | Beginner | City Travel
Many posts use Dijkstra, I look to explore dfs with memoization in this post\n\nAlgorithm\n1. Bulid the graph. Keep only minimum weights edges between two citie
Many posts use Dijkstra, I look to explore dfs with memoization in this post\n\n**Algorithm**\n1. Bulid the graph. Keep only minimum weights edges between two cities.\n2. Start dfs from city 0 with maxTime remaining.\n3. From a city ```u``` travel to all cities ```v``` using dfs if time does not run out (i.e time does not go below 0). Choose the city ```v ``` which takes minimum fees.\n4. If you reach the final city return the fee for final city as the answer.\n6. We memoize on fees using ```city number``` and ```time```.\n\n**Code**\n```\nclass Solution {\npublic:\n    int n;\n\t//  {key = city u, value = {key = city v, value = time required to travel from city u to v} }\n    vector<unordered_map<int, int>> graph;\n    vector<vector<int>>dp;\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& fee) {\n        n = fee.size();\n        dp = vector<vector<int>>(n, vector<int>(maxTime+1, -1));\n        graph = vector<unordered_map<int, int>>(n);\n        // build the graph, keep weights which are minimum if multiple paths are present between same pair of nodes\n        for(auto &e : edges){\n            if(graph[e[0]].count(e[1]) == 0) graph[e[0]][e[1]] = e[2];\n            else graph[e[0]][e[1]] = min(graph[e[0]][e[1]], e[2]);\n            if(graph[e[1]].count(e[0]) == 0) graph[e[1]][e[0]] = e[2];\n            else graph[e[1]][e[0]] = min(graph[e[1]][e[0]], e[2]);\n        }\n        int ans = dfs(fee, 0, maxTime);\n        return ans == INT_MAX ? -1 : ans;\n    }\n    \n    int dfs(vector<int>& fee, int u, int time){\n        if(u == n-1) return fee[u];\n        if(dp[u][time] != -1) return dp[u][time];\n        \n        int ans = INT_MAX;\n        for(auto &e : graph[u]){\n            int v = e.first;\n            int vtime = e.second;\n            if(time - vtime >= 0){\n                int val = dfs(fee, v, time-vtime);\n                if(val != INT_MAX){\n                    ans = min(ans, fee[u] + val);\n                }\n            }\n        }\n        return dp[u][time] = ans;\n    }\n};\n```
['Depth-First Search', 'Memoization', 'C']