929 - Number Maze

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#define M 1001
#define MAXINT 2147483640
using namespace std;

long G[M][M],d[M][M],m,n;
long next[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
bool Visited[M][M];
long DjKastra(long,long);
struct coord
{
    int key,x,y;
    bool operator<(const coord& c) const
    {
        if(key < c.key)
            return false;
        return true;
    }
};

int main()
{
    long t,i,j,k=1,c;
    //freopen("in.txt","r",stdin);
    scanf("%ld",&t);

    while(t--)
    {
        scanf("%ld%ld",&m,&n);
        for(i=1;i<=m;i++)
            for(j=1;j<=n;j++)
                scanf("%ld",&G[i][j]);

        c = DjKastra(m,n);
        printf("%ld\n",c);
    }
    return 0;
}

long DjKastra(long m,long n)
{
    priority_queue < coord >Q;
    struct coord tmp;
    long i,j,x,y,tx,ty,tc;
   
    for(i=0;i<M;i++)
        for(j=0;j<M;j++)
            d[i][j] = MAXINT,Visited[i][j]=false;
   
    d[1][1] = G[1][1];
    tmp.key = 0,tmp.x = tmp.y = 1;
    Q.push(tmp);
   
    while(!Q.empty())
    {
        tmp = Q.top();Q.pop();

        x = tmp.x;
        y = tmp.y;
        Visited[x][y] = true;

        for(i=0;i<4;i++)
        {
            tx = x + next[i][0];
            ty = y + next[i][1];

            if(tx>=1&&tx<=m&&ty>=1&&ty<=n&&Visited[tx][ty]==false)
            {
                tc = d[x][y] + G[tx][ty];
                if (tc < d[tx][ty])
                {
                    d[tx][ty] = tc;
                    tmp.x = tx;tmp.y = ty;
                    tmp.key = d[tx][ty];
                    Q.push(tmp);
                }
            }
        }
    }
    return d[m][n];
}