POPTUNNL - Editorial

editorial
, , , ,
43

Can we use Dijkstra Aglo ?? As i have used but the code is giving WA.

#include <bits/stdc++.h>
#include
#include
#include
#include <unordered_map>
#include
#define ll long long int
#define mod 1000000007
#define MAX 8001

using namespace std;

int get_min(int* distance, int* visited, int n)
{
int ans = -1;
for(int i=0; i<n; i++)
{
if(!visited[i] && (ans == -1 || distance[i] < distance[ans]))
ans = i;
}

return ans;

}

void dijsktra(int** edge, int n)
{
int* distance = new int [n];
int* visited = new int n;

for(int i=0; i<n; i++)
    distance[i] = INT_MAX;
distance[0] = 0;

for(int i=0; i<n; i++)
{
    int minval = get_min(distance, visited, n);
    visited[minval] = 1;
    for(int j=0; j<n; j++)
    {
        if(edge[minval][j] != 0 && !visited[j] && distance[j] > distance[minval] + edge[minval][j])
        {
            distance[j] = distance[minval] + edge[minval][j];
        }
    }
}

if(distance[n-1] == INT_MAX)
	cout << "-1" << endl;
else
	cout << distance[n-1] << endl;

}

int main()
{
int t;
cin >> t;
while(t–)
{
int n, k;
cin >> n >> k;
string s[n];
for(int i=0; i<n; i++)
cin >> s[i];

	int** edge = new int*[n];
	for(int i=0; i<n; i++)
	{
		edge[i] = new int[n];
		for(int j=0; j<n; j++)
			edge[i][j] = 0;
	}

	for(int i=0; i<n; i++)
	{
		int l = i-k, u = i+k;
		if(l<0)
			l = 0;
		if(u >= n)
			u = n-1;

		for(int j=l; j<=u; j++)
		{
			if(i == j)
				continue;

			if(s[i][j] == '1')
				edge[i][j] = 1;
		}

	}

	dijsktra(edge, n);
}

}