UVA 929  Number Maze Dijkstra based problem. We have already discussed Dijkstra algorithm for shortest path from source to destination here http://wikistack.com/shortest-path-problem-dijkstras-algorithm/. The given problem at this link https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=870 is based on Dijkstra’ algorithm. Let us practice it for applying Dijkstra algorithm.

Your are give a maze filled with some numbers from 0 to 9, find the min cost to reach from top left corner to bottom right corner. The maze can be traversed following any orthogonal direction (i.e.,north, south, east and west).

```#include<iostream>
#include<climits>
#include<cstring>
#include<cstdio>
using namespace std;

#define INF 1000000000
#define N 1000
#define M 1000

int g[N][M];
int dist[N][M];
int visited[N][M];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

bool isSafe(int x, int y, int row, int col)
{
if (x >= 0 && x < row && y >= 0 && y < col
&& dist[x][y] != 0 && !visited[x][y])
return true;

return false;
}

void minindex (int &x, int &y, int row, int col)
{
int min = INF;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (dist[i][j] < min && !visited[i][j])
{
min = dist[i][j];
x = i;
y = j;
}
}
}
}

void dijk (int u, int v, int &ans, int row, int col)
{
dist[u][v] = 0;

for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
int x;
int y;
minindex (x, y, row, col);
visited[x][y] = 1;
for (int ii = 0; ii < 4; ii++)
{
int xx = x + dx[ii];
int yy = y + dy[ii];
if (isSafe(xx,yy,row,col))
{
if (dist[xx][yy] > dist[x][y] + g[xx][yy])
{
dist[xx][yy] = dist[x][y] + g[xx][yy];
}
}
}

}
}
ans = dist[row - 1][col - 1];
}

int
main ()
{
freopen ("929.txt", "r", stdin);
int t = 0;
cin >> t;
for (int test = 0; test < t; test++)
{
int row = 0;
int col = 0;
int ans = 0;
cin >> row >> col;
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
dist[i][j] = INF;
visited[i][j] = false;
g[i][j] = 0;
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cin >> g[i][j];
}
}

dijk (0, 0, ans, row, col);
cout << ans << endl;
ans = 0;
}	// test end
return 0;
}```