C++ solution || Dijkstra's Algorithm Approach
\n# Complexity\n- Time complexity:\nO(Elog(V))\n- Space complexity:\nO(V)\n# Code\n\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>
\n# Complexity\n- Time complexity:\n$$O(Elog(V))$$\n- Space complexity:\n$$O(V)$$\n# Code\n```\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n      int n = passingFees.size();\n      vector<int>costs(n,INT_MAX);\n      vector<int>totaltime(n,INT_MAX);\n      costs[0] = passingFees[0];\n      totaltime[0] = 0;\n      vector<vector<pair<int,int>>>graph(n);\n      for(auto nxt : edges){\n        graph[nxt[0]].push_back({nxt[1],nxt[2]});\n        graph[nxt[1]].push_back({nxt[0],nxt[2]});\n      }\n      priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>>pq;\n      ////////// {cost, node, time}\n      pq.push({costs[0],{totaltime[0],0}});\n\n      while (!pq.empty())\n      {\n        int paid = pq.top().first, time = pq.top().second.first, node = pq.top().second.second;\n        pq.pop();\n        \n        for(auto it : graph[node]){\n          if(time+it.second <= maxTime){\n            if(paid + passingFees[it.first] < costs[it.first]){\n              costs[it.first]=paid+passingFees[it.first];\n              totaltime[it.first] = time+it.second;\n              pq.push({costs[it.first], {totaltime[it.first], it.first}});\n            }else if(time + it.second < totaltime[it.first]){\n              totaltime[it.first] = time+it.second;\n              pq.push({paid+passingFees[it.first], {totaltime[it.first], it.first}});\n            }\n            \n          }\n        }\n      }\n      if(costs[n-1] != INT_MAX){\n        return costs[n-1];\n      }\n      return -1;\n    }\n};\n```
['Breadth-First Search', 'Graph', 'Shortest Path', 'C++']