C++ Solution | Dijkstra’s Algorithm
Solution\n\nThe problem can be solved using standard Dijkstra algorithm with slight modifications.\n\n- In priority queue for each vertex a vector corresponding
**Solution**\n\nThe problem can be solved using standard Dijkstra algorithm with slight modifications.\n\n- In priority queue for each vertex a vector corresponding to {cost, time, vertex} is stored.\n- The priority queue will be a min-heap, the vectors will be arranged first by cost and then by time.\n- Source vertex (0) will be push into min-heap first.\n- Follow the standard dijkstra by popping vertices and traverse the connected edges.\n- The difference here will be that only those edges will be traversed which will not cause the time to exceed  `maxTime`.\n- Also a new entry will be pushed to heap if the cost or time of vertex will reduce.\n- At the end return the cost of destination vertex(`dest`).\n\n**Note**: The reason for including extra condition which is allowing to traverse edges which cause the time to reduce is that it is possible that these edges led us to destination. However if we just traverse those edge causing cost to decrease then we are ignoring the time which can lead us to a non-optimal answer or even a case where time exceed the `maxTime` leading us to return `-1`.\n\n**Code**\n```\nclass Solution {\npublic:\n    vector<vector<int>> adj[1001];\n    int cost[1001], time[1001];\n    \n    int dijkstra(int src, int dest, int maxTime) {\n        \n        for (int i = 1; i <= dest; i++) {\n            cost[i] = INT_MAX;\n            time[i] = INT_MAX;\n        }\n        \n        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;\n        pq.push({cost[src], time[src], src});\n        \n        while (pq.empty() == 0) {\n            vector<int> z = pq.top(); pq.pop();\n            \n            int c = z[0];     // cost\n            int t = z[1];     // time\n            int v = z[2];     // vertex\n            \n            for (int i=0;i<adj[v].size();i++) {\n                \n\t\t\t    // if this edge does not cause the time to exceed maxTime\n                if (t + adj[v][i][1] <= maxTime) {\n                    \n\t\t\t\t    // if cost will decrease\n                    if (cost[adj[v][i][0]] > c + adj[v][i][2]) {\n                        cost[adj[v][i][0]] = c + adj[v][i][2];\n                        \n                        time[adj[v][i][0]] = t + adj[v][i][1];\n                        pq.push({cost[adj[v][i][0]], time[adj[v][i][0]], adj[v][i][0]});\n                    }\n                    \n\t\t\t\t\t// if time will decrease\n                    else if (time[adj[v][i][0]] > t + adj[v][i][1]) {\n                        time[adj[v][i][0]] = t + adj[v][i][1];\n                        pq.push({c + adj[v][i][2], time[adj[v][i][0]], adj[v][i][0]});\n                    }\n                }\n            }\n        }\n        \n        return cost[dest];\n    }\n    \n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& fee) {\n        int i, x, y, t, e = edges.size(), n = fee.size();\n        \n        for (i=0;i<e;i++) {\n            x = edges[i][0];\n            y = edges[i][1];\n            t = edges[i][2];\n            \n            adj[x].push_back({y, t, fee[y]});\n            adj[y].push_back({x, t, fee[x]});\n        }\n        \n        cost[0] = fee[0];\n        time[0] = 0;\n        \n        int ans = dijkstra(0, n-1, maxTime);\n        \n        if(ans == INT_MAX)\n            return -1;\n        \n        return ans;\n    }\n};\n```
[]