Modified Dijkstra's
We run Dijkstra, and for each node we track the sorted list of {fee, time}. This allows us to prune costly paths that do not save us time.\n \nI initially did n
We run Dijkstra, and for each node we track the sorted list of `{fee, time}`. This allows us to prune costly paths that do not save us time.\n \nI initially did not use the min heap for the queue, and got TLE. \n\n**C++**\n```cpp\nint minCost(int maxTime, vector<vector<int>>& edges, vector<int>& fees) {\n    vector<set<array<int, 2>>> state(fees.size()); // city: {fee, time}\n    vector<vector<array<int, 2>>> al(fees.size()); // city i : {city j, time}\n    for (auto &e : edges) {\n        al[e[0]].push_back({e[1], e[2]});\n        al[e[1]].push_back({e[0], e[2]});\n    }\n    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q;\n    q.push({fees[0], 0, 0}); // {fee, time, city}\n    while(!q.empty()) {\n        auto [fee, time, city] = q.top(); q.pop();\n        if (city == fees.size() - 1)\n            return fee;\n        for (auto [city1, time1] : al[city]) {\n            if (time + time1 <= maxTime) {\n                auto it = state[city1].upper_bound({fee + fees[city1], time + time1});\n                if (it == begin(state[city1]) || (*prev(it))[1] > time + time1) {\n                    state[city1].insert({fee + fees[city1], time + time1});\n                    q.push({fee + fees[city1], time + time1, city1 });\n                }\n            }\n        }\n    }\n    return -1;\n}\n```
['C']