UVA 929 - Number Maze(cpp file)

Problem Type : Dijkstra



#include<bits/stdc++.h>
#define MAX 1000
#define INF 1000000
using namespace std;

struct node
{
    int x,y,c;

    node(int d,int e,int f)
    {
        x=d;
        y=e;
        c=f;
    }
    bool operator<(const node &p)const
    {
        return c>p.c;
    }
};
int vertex,edge;
int mat[MAX][MAX],dist[MAX][MAX];
int X[4]= {1,-1,0,0};
int Y[4]= {0,0,-1,1};
priority_queue<node>Q;
void djkstra()
{
    while(!Q.empty())
    {
        Q.pop();
    }
    int ux,uy,vx,vy,i,j;

    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=edge; j++)
        {
            dist[i][j]=INF;
        }
    }
    Q.push(node(1,1,mat[1][1]));
    dist[1][1]=mat[1][1];
    while(!Q.empty())
    {
        node top = Q.top();
        Q.pop();
        ux = top.x;
        uy = top.y;

        for(i=0; i<4; i++)
        {
            vx= ux+X[i];
            vy= uy+Y[i];
            if(vx>=1 && vx<=vertex && vy>=1 && vy<=edge)
            {
                if(dist[vx][vy]>dist[ux][uy]+mat[vx][vy])
                {
                    dist[vx][vy]=dist[ux][uy]+ mat[vx][vy];
                    Q.push(node(vx,vy,dist[vx][vy]));
                }
            }

        }

    }
}
int main()
{
    int i,j,test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d",&vertex,&edge);
        for(i=1; i<=vertex; i++)
        {
            for(j=1; j<=edge; j++)
            {
                scanf("%d",&mat[i][j]);
            }
        }
        djkstra();
        printf("%d\n",dist[vertex][edge]);
    }

}