Tag lexicographically smallest path

SPOJ – DIGOKEYS – Find the Treasure

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/DIGOKEYS/

Note: This problem is pretty much a simple Graph problem. I have solved this using BFS. One thing that I was confused about was how to handle the “lexicographically smallest order of path“. But after writing the basic code, the idea that came to my mind is how about if I sort the initial graph while building that by inserting the edge nodes. If the edges are sorted, then while running the BFS, it will automatically choose the smallest numbers first! That solves our finding of “lexicographically smallest order of path”. Please feel free to comment below if you have any other ideas to implement this.

Code:

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
int parent[MAX];

void path_print(int dst, int ans)
{
    vector<int> path;
    dst=parent[dst]; //As the question suggests not to include the last destination which is obvious in every case
    while(dst!=-1)
    {
        path.push_back(dst);
        dst=parent[dst];
    }
    cout<<path[ans-1];
    for(int i=ans-2; i>=0; i--) cout<<" "<<path[i];
    cout<<endl;
}


int bfs(int src, int dst, vector<vector<int> > &g)
{
    int vis[MAX]={0};
    int dis[MAX];
    vis[src]=1;
    dis[src]=0;
    parent[MAX]={-1};
    parent[src]=-1;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==dst) return dis[u];
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=1;
                dis[v]=dis[u]+1;
                parent[v]=u;
                q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<vector<int> > g(MAX, vector<int> (11));
        for(int j=1; j<n; j++)
        {
            int edge;
            cin>>edge;
            int src=j;
            vector<int> des; //for sorting the edges// for "lexicographical" purpose
            for(int k=0; k<edge; k++)
            {
                int dst;
                cin>>dst;
                des.push_back(dst);
            }
            sort(des.begin(), des.end()); //We are doing this only to ensure the "lexicographically smallest" order of path
            for(int k=0; k<des.size(); k++)
            {
                g[src].push_back(des[k]);
            }

        }
        int ans=bfs(1,n, g);
        cout<<ans<<endl;
        if(ans!=-1)
        {
            path_print(n, ans);
        }
        cout<<endl;
    }
    return 0;
}