UVa 929 - Number Maze

/*

    Accepted

    Algorithm: Dijkstra

    The sample of this problem is also solvable using BFS algorithm, but to find
    minimum the problem is an optimization problem. So, the Dijkstra algorithm is
    perfect for it. This is straight forward Dijkstra. But, you should visit
    each position (x, y) as one time to avoid TLE.

*/

#include<bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define psb push_back
#define fast ios_base::sync_with_stdio(false)

typedef map<string, int>mpsi;
typedef map<int, string>mpis;
typedef long long LL;

const int high = 1005;
const int inf = (1 << 31) - 1;

vector<LL>adj[high];
vector<LL>nodelist;

int matrix[high][high], visited[high][high], cost[high][high];
int N , M , test;

int move_x[] = {1, -1, 0, 0};
int move_y[] = {0, 0, 1, -1};

struct data
{
    int node1, node2, cost;

    data() { }

    data(int n1 , int n2, int c)
    {
        node1 = n1;
        node2 = n2;
        cost = c;
    }

    bool operator<(const data &b)const
    {
        return cost > b.cost;
    }
};

void CLR()
{
    for(int i=0; i<high; i++)
    {
        for(int j=0; j<high; j++)
        {
            matrix[i][j] = 0;
            visited[i][j] = 0;
            cost[i][j] = inf;
        }
    }
}

void matrix_input(int n , int m)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            sf("%d", &matrix[i][j]);
        }
    }
}

void Call_Dijkstra(int sx, int sy, int dx, int dy)
{
    visited[sx][sy] = 1;

    cost[sx][sy] = matrix[sx][sy];

    priority_queue<data>Q;

    Q.push(data(sx, sy, matrix[sx][sy]));

    while(!Q.empty())
    {
        int ux = Q.top().node1;
        int uy = Q.top().node2;
        int c = Q.top().cost;

        Q.pop();

        if(ux == dx && uy == dy) return;

        for(int i=0; i<4; i++)
        {
            int vx = ux + move_x[i];
            int vy = uy + move_y[i];

            if(!visited[vx][vy] && (vx>=0 && vx<N) && (vy>=0 && vy<M))
            {
                if(cost[vx][vy] == inf)
                {
                    cost[vx][vy] = cost[ux][uy] + matrix[vx][vy];
                    Q.push(data(vx, vy, cost[vx][vy]));
                }

                else
                {
                    cost[vx][vy] = min(cost[vx][vy], cost[ux][uy] + matrix[vx][vy]);
                    Q.push(data(vx, vy, cost[vx][vy]));
                }

                visited[vx][vy] = 1;
            }
        }
    }
}


int main()
{
    fast;
    int i , j;

    //cout << inf;

    sf("%d", &test);

    while(test--)
    {
        CLR();

        sf("%d %d", &N, &M);

        matrix_input(N , M);

        Call_Dijkstra(0 , 0, N-1, M-1);

        pf("%d\n", cost[N-1][M-1]);
    }

    return 0;
}