[C++] Dijkstra's algorithm | Intuitive | Beats 99 %
\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& fee) {\n        int n = fee.size();\n        vector<vector<pa
```\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& fee) {\n        int n = fee.size();\n        vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());\n        \n        for(vector<int>& e: edges){\n            int u = e[0], v = e[1], t = e[2];\n            adj[u].push_back({t, v});\n            adj[v].push_back({t, u});\n        }\n        \n        vector<int> times(n, maxTime + 1);\n        auto cmp = [](auto& a, auto& b) {return a[0] > b[0];};\n        priority_queue<array<int, 3>, vector<array<int, 3>>, decltype(cmp)> q(cmp);\n        \n        q.push({fee[0], 0, 0});\n        \n        while(q.size() > 0){\n            auto [price, t, u] = q.top();\n            q.pop();\n            \n            if(u == n - 1) return price;\n            \n            //if we already process \'u\' (than previously it had smaller price)\n            //and if then it had time at most \'t\' time we can skip\n            //otherwise \'t\' is the smallest time for \'u\' until now\n            if(times[u] <= t) continue;\n            else times[u] = t;\n            \n            for(auto& [t1, v]: adj[u]){\n                //again same reasoning\n                if(times[v] <= t + t1) continue;\n                q.push({price + fee[v], t1 + t, v});\n            }\n        }\n        return -1;\n    }\n};\n```
[]