Spoj PPATH

I am trying to solve the following problem from spoj:
https://www.spoj.com/problems/PPATH/
Here is my solution to it:

I am not able to figure out why this code is not giving correct answer. I am generating a graph of all 4 digit primes between source and destination number and using bfs but its giving wrong answers. Please help.

I think you should use function generate graph for src=1000 to dest=9999 at the start only. This will create adjacency list for all. Now you should call bfs for each TC.

#include <bits/stdc++.h>
using namespace std;

#define lld long long int 

vector <int> lst[100000];
int prime[100000]={0};
vector <int> v;

void seive()
{
    for(int i=4;i<=9999;i+=2)
    prime[i]=1;
    for(int i=3;i<=sqrt(9999);i+=2)
    {
        if(prime[i]==0)
        {
            for(int j=i*i;j<=9999;j+=i)
            prime[j]=1;
        }
    }
    for(int i=1000;i<=9999;i++)
    if(prime[i]==0)
        v.push_back(i);
}

void fun()
{
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<v.size();j++)
        {
            vector <int> temp;
            int val=v[i],val1=v[j];
            while(val>0)
            {
                int x=val%10;
                int y=val1%10;
                temp.push_back(abs(x-y));
                val/=10;
                val1/=10;
            }
            sort(temp.begin(),temp.end());
            if(temp[0]==0&&temp[1]==0&&temp[2]==0&&temp[3]!=0)
            lst[v[i]].push_back(v[j]);
        }
    }
}
int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    seive();
    fun();
    while(t--)
    {
        int vis[100000]={0};
        int res[100000]={-1};
        memset(res,-1,sizeof(res));
        int n,k,a,b;
        cin>>n;
        cin>>k;
        queue <int> q;
        q.push(n);
        vis[n]=1;
        res[n]=0;
        while(!q.empty())
        {
            a=q.front();
            //cout<<a<<" "<<res[a]<<endl;
            q.pop();
            if(a==k)
            break;
            for(int i=0;i<lst[a].size();i++)
            {
                if(vis[lst[a][i]]==0)
                {
                    vis[lst[a][i]]=1;
                    res[lst[a][i]]=res[a]+1;
                    q.push(lst[a][i]);
                }
            }
        }
        if(res[k]==-1)
        cout<<"Impossible\n";
        else
        cout<<res[k]<<"\n";
    }
    return 0;
}

You may see this.

1 Like

But you are also using 4 digit primes, aren’t you?. Moreover , are you saying that there is some problem in my generate graph function? I tried constructing graph for all primes from 2 to 9999 but still its giving wrong answer. Not able to understand what am i missing.

In function generate graph your arguments are a and b. So, it is checking all the primes between them. There may be chance that you can reach the dest number faster if you chose a prime that is outside their range

There seems to be a problem with the isConnected function. When I instead tried to check if two primes are connected with an edge using your method above, I got AC on spoj using 4 digit primes only.
But using my method Its giving wrong answer. Do you know why? See this AC solution

Thanks :slightly_smiling_face: