C++ | DP (Recursive) | Dijkstra (Two Approach)
Code: (Using dp)\n\nclass Solution{\npublic:\n    int dp[1002][1002], n;\n    int solve(int maxTime, int src, vector<int> &cost, vector<pair<int, int>> g[])\n  
# Code: (Using dp)\n```\nclass Solution{\npublic:\n    int dp[1002][1002], n;\n    int solve(int maxTime, int src, vector<int> &cost, vector<pair<int, int>> g[])\n    {\n        if (maxTime < 0)\n            return 1e9;\n\n        if (src == n - 1)\n            return maxTime >= 0 ? cost[n - 1] : 1e9;\n\n        if (dp[maxTime][src] != -1)\n            return dp[maxTime][src];\n\n        int ans = 1e9;\n        for (auto [child, time] : g[src])\n            ans = min(ans, cost[src] + solve(maxTime - time, child, cost, g));\n\n        return dp[maxTime][src] = ans;\n    }\n\n    int minCost(int maxTime, vector<vector<int>> &edges, vector<int> &cost)\n    {\n        n = cost.size();\n        vector<pair<int, int>> g[n];\n        memset(dp, -1, sizeof(dp));\n        for (auto edge : edges)\n        {\n            g[edge[0]].push_back({edge[1], edge[2]});\n            g[edge[1]].push_back({edge[0], edge[2]});\n        }\n        int ans = solve(maxTime, 0, cost, g);\n        return ans == 1e9 ? -1 : ans;\n    }\n};\n\n```\n\n\n# Code: (Using Dijkstra)\n```\nclass Solution {\npublic:\n    struct comp{\n        int fees, time, node;\n    };\n\n    struct graph_comp{\n        int child, time, fees;\n    };\n\n    struct myCmp{\n        bool operator()(comp below, comp above)\n        {\n            if(below.fees == above.fees)\n                return below.time > above.time;\n            \n            return below.fees > above.fees;\n        }\n    };\n\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int n = passingFees.size();\n        vector<graph_comp> g[n];\n        for(auto edge : edges)\n        {\n            g[edge[0]].push_back({edge[1], edge[2], passingFees[edge[1]]});\n            g[edge[1]].push_back({edge[0], edge[2], passingFees[edge[0]]});\n        }\n\n        priority_queue<comp, vector<comp>, myCmp> pq;\n        vector<int> cost(n, 1e9);\n        vector<int> time(n, 1e9);\n\n        cost[0] = passingFees[0];\n        time[0] = 0;\n        pq.push({cost[0], time[0], 0});\n\n        while(!pq.empty())\n        {\n            auto par = pq.top();\n            pq.pop();\n\n            for(auto curr : g[par.node])\n            {\n                if(par.time + curr.time > maxTime)\n                    continue;\n                \n                if(cost[curr.child] > par.fees + curr.fees)\n                {\n                    cost[curr.child] = par.fees + curr.fees;\n                    time[curr.child] = par.time + curr.time;\n                    pq.push({cost[curr.child], time[curr.child], curr.child});\n                }\n                else if(time[curr.child] > par.time + curr.time)\n                {\n                    time[curr.child] = par.time + curr.time;\n                    pq.push({par.fees + curr.fees, time[curr.child], curr.child});\n                }\n\n            }\n        }\n\n        return cost[n - 1] == 1e9 ? -1 : cost[n - 1];\n    }\n};\n```
['Dynamic Programming', 'Graph', 'Recursion', 'Shortest Path', 'C++']