Dijkstra with one extra state | c++
I hope you are clear with 1st part of the problem where this move_made part was not there and rest was the same problem\nlink to my editorial for that problem -
I hope you are clear with 1st part of the problem where this move_made part was not there and rest was the same problem\nlink to my editorial for that problem - https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/discuss/6000326/Dijkstra-or-Graph-or-c%2B%2B\n\nso here the extra catch is :\n**Moving between adjacent rooms takes one second for one move and two seconds for the next, alternating between the two.**\nwe can simply have one more state which will store number of moves mode so far so that we can check if even then 1 if odd then 2, rest everything is same , the code goes like\n```\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>& mt) {\n        int n = mt.size();\n        int m = mt[0].size();\n    vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n    \n   \n    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<>> pq;\n    pq.push({0, 0, 0, 0});\n    \n   \n    vector<vector<int>> time_taken(n, vector<int>(m, INT_MAX));\n    time_taken[0][0] = 0;\n    \n    while (!pq.empty()) {\n        auto [time, x, y, moves_made] = pq.top();\n        pq.pop();\n      \n        if (x == n - 1 && y == m - 1) {\n            return time;\n        }\n        \n        for (auto& dir : dirs) {\n            int nx = x + dir[0];\n            int ny = y + dir[1];\n            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {\n               \n                int move_duration = (moves_made % 2 == 0) ? 1 : 2; \n           \n                int wait_time = max(time+move_duration, mt[nx][ny] + move_duration);\n             \n                if (wait_time < time_taken[nx][ny]) {\n                    time_taken[nx][ny] = wait_time;\n                    pq.push({wait_time, nx, ny, moves_made + 1});\n                }\n            }\n        }\n    }\n    \n    return -1; \n    }\n};\n```\nsince we had one extra constraint we added one more state to check and redefined our edges , everything else remains same.\n\nI have solved CSES graph problems , you can check that out here if you face issues in implementing graph algorithms\nhttps://www.youtube.com/watch?v=6owaCOCWLu0&list=PLQr1KWjS3pAGRjsSp3kcULieEgogfOGj9\n
['C']