C++ 2 Solutions | DP | Dijkstra's Algorithm
Dynamic Programming\n\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int PASS_MAX = 1
Dynamic Programming\n```\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int PASS_MAX = 10000000;\n        vector<vector<int>> dp(maxTime + 1, vector<int>(passingFees.size(), PASS_MAX));\n        \n        dp[0][0] = passingFees[0];\n        for (int i=1; i<=maxTime; ++i) {\n            for (int j=0; j<edges.size(); ++j) {\n                if (edges[j][2] > i) {\n                    continue;\n                }\n                int city1 = edges[j][0];\n                int city2 = edges[j][1];\n                int time = edges[j][2];\n                dp[i][city1] = min(dp[i][city1], dp[i - time][city2] + passingFees[city1]);\n                dp[i][city2] = min(dp[i][city2], dp[i - time][city1] + passingFees[city2]);\n            }\n        }\n        int ans = PASS_MAX;\n        for (int i=0; i<=maxTime; ++i) {\n            ans = min(ans, dp[i][passingFees.size()-1]);\n        }\n        if (ans == PASS_MAX) {\n            return -1;\n        }\n        return ans;\n    }\n};\n// Time : O(TE) T = maxtime E = edge\n// Space : O(TN)\n```\nDijkstra\'s Algorithm\n```\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int n = passingFees.size();\n        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> myHeap;\n        \n        vector<vector<pair<int, int>>> edge (n, vector<pair<int, int>>());\n        for (int i=0; i<edges.size(); ++i) {\n            edge[edges[i][0]].push_back({edges[i][1], edges[i][2]});\n            edge[edges[i][1]].push_back({edges[i][0], edges[i][2]});\n        }\n        vector<int> dist(n, INT_MAX);\n        dist[0] = 0;\n        myHeap.push({passingFees[0], {0, 0}});\n        while (!myHeap.empty()) {\n            int node = myHeap.top().second.first;\n            int fee = myHeap.top().first;\n            int time = myHeap.top().second.second;\n            myHeap.pop();\n            \n            if (node == n - 1) {\n                return fee;\n            }\n            for (int i=0; i<edge[node].size(); ++i) {\n                int neighbor = edge[node][i].first;\n                int travel_time = edge[node][i].second;\n                if (time + travel_time > maxTime) {\n                    continue;\n                }\n                if (dist[neighbor] > time + travel_time) {\n                    dist[neighbor] = time + travel_time;\n                    myHeap.push({fee + passingFees[neighbor], {neighbor, time + travel_time}});\n                }\n            }\n        }\n        return -1;\n    }\n};\n// Time : O(Elogn)\n// Space : O(n + E)\n```
['Dynamic Programming', 'C']