Dijkstra | C++
Complexity\n- Time complexity: O(nm*log(nm))\n Add your time complexity here, e.g. O(n) \n\n# Code\ncpp []\n#define ll long long int\n\nclass Solution {\npublic
# Complexity\n- Time complexity: $$O(nm*log(nm))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#define ll long long int\n\nclass Solution {\npublic:\n    int dr[4] = {0, 1, 0, -1};\n    int dc[4] = {1, 0, -1, 0};\n\n    int minTimeToReach(vector<vector<int>>& mt) {\n        int n=mt.size(), m=mt[0].size();\n        priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>>pq;\n        vector<vector<ll>>dist(n, vector<ll>(m, LLONG_MAX));\n        dist[0][0]=0;\n        pq.push({0, 0, 0, 2});\n        while(!pq.empty()){\n            auto t = pq.top();\n            pq.pop();\n            ll d = t[0];\n            int x=t[1], y=t[2], c=t[3];\n            if(x==n-1 && y==m-1)return d;\n            if(d>dist[x][y])continue;\n            for(int i=0;i<4;i++){\n                int nx=x+dr[i], ny=y+dc[i];\n                if(nx>=0 && nx<n && ny>=0 && ny<m){\n                    ll k = max((ll)0, mt[nx][ny]-d);\n                    if(c==2)k+=1;\n                    else k+=2;\n                    if(dist[nx][ny] > (d + k)){\n                        dist[nx][ny]= (d + k);\n                        if(c==2)pq.push({dist[nx][ny], nx, ny, 1});\n                        else pq.push({dist[nx][ny], nx, ny, 2});\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n};\n```
['Shortest Path', 'C++']