Minimum Cost Path,,we can go (i,j-1), (i, j+1), (i-1, j), (i+1, j). (Dijkstra's Algorithm)

problem link::https://practice.geeksforgeeks.org/problems/minimum-cost-path3833/1

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int n;
const int mx = 505;
vector<vector<int>> grid;
int dis[mx][mx];
int dir_x[4] = {1, -1, 0, 0};
int dir_y[4] = {0, 0, 1, -1};

void solve(int x, int y) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dis[i][j] = 1e5;
        }
    }
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pr;
    pr.push({grid[0][0], {0, 0}});
    dis[0][0] = grid[0][0];
    while (!pr.empty()) {
        pair<int, int> node = pr.top().second;
        int cost = pr.top().first;
        pr.pop();
        if (dis[node.first][node.second] < cost)continue;
        for (int m = 0; m < 4; m++) {
            int x1 = node.first + dir_x[m];
            int y1 = node.second + dir_y[m];
            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < n && cost + grid[x1][y1] < dis[x1][y1]) {
                dis[x1][y1] = cost + grid[x1][y1];
                pr.push({cost + grid[x1][y1], {x1, y1}});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        vector<int> vec;
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            vec.push_back(x);
        }
        grid.push_back(vec);
    }
    solve(0, 0);
    cout << dis[n - 1][n - 1] << endl;
    return 0;
}

struct min {
    volatile int s = 0;
    filesystem::file_time_type ;

};