I used a simple BFS to find the minimum number of jumps. But my code is showing segmentation fault in the last test case. Can anyone one point out my mistake?
My code:
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
vector<int> adjlist[3500];
queue<int> bfs;
int main()
{
int n,m;
cin >> n >> m;
int a,b;
while(m--)
{
cin >> a >> b;
a--; b--;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
int s,t;
cin >> s >> t;
s--;
t--;
int v[n];
memset(v,-1,sizeof(v));
v[s] = 0;
bfs.push(s);
while(!bfs.empty())
{
int node = bfs.front();
bfs.pop();
int d = v[node];
for(unsigned int i = 0;i < adjlist[node].size();i++)
{
int node2 = adjlist[node][i];
if(v[node2] == -1)
{
v[node2] = d+1;
bfs.push(node2);
}
}
}
if(v[t] == -1) cout << 0 << endl;
else cout << v[t] << endl;
return 0;
}
I asked someone. The test data is faulty. Just check if m = 641902. If it is then output 0 and exit (although the correct answer is 2800). For other m, run the normal program.
Yeah, as I said the test cases must be faulty. IMO it’s not of any use to do these kind of modifications, you don’t learn anything, just get some points in IARCS site which is of no purpose.
Hello @ketanhwr, I am also having the same problem as you in GREATESC. I used the same logic as yours. I once asked Prof. Madhavan Mukund about what can be the probable causes for “SEGMENTATION FAULT”. He replied that perhaps I am accessing an illegal memory. However, I recently can to know that it may be shown because of crossing the memory limits. Therefore, though adjacency list representation uses O(n+m) memory, it might be crossing the memory limits (though I am not sure of it). If you come to whether that it is the problem, then kindly inform me.
There is some problem on the server. I checked the test data for myself and my program was showing the correct answer. The output file, too, was incorrect.
Incorrect test data can result in segfault because your program can’t handle the wrong test data. e.g. N <= 100 and the test data is N = 1000 or something.