HackerEarth IRCTC problem solution

In this HackerEarth IRCTC problem solution Good news , You have a chance to work in IRCTC as a software developer . Applications are required with a program for railway sites . sid of a station is a something which uniquely defines it . Given N station’s sid from 1 to N and distance between any two stations , if any person wants to go from station having sid A to another station C via station B as early as possible , where time is directly proportional to distance . What you have to do is to print the total distance and path to be covered by train if it exists , otherwise print “No Train Found.”. If a railway line connects station A to B with distance d than it means it will also connects station B to station A with same distance d .

HackerEarth IRCTC problem solution.

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

#define pii pair<long long int,int>
#define MAX 100000000000000000

pii p ;
multiset<pii> myset ;

long long int dist[100004] ;
bool visited[100004] ;
int path[100004] ;
vector< pii> graph[100004] ;

void dijikstra(int a, int b , int v ) {


        memset( visited , false , sizeof(visited) ) ;

    for( int i = 0 ; i <= v ; i++ ) dist[i] = MAX ;

    dist[a] = 0 ;//distance of source from source is 0...
    visited[a] = true ;

    //making pair...
    p.first = dist[a] ;
    p.second = a ;

    myset.insert(p) ;//inserting first pair in set ;

    //cout << "entering algo : " << endl ;
    while( !myset.empty() ) {

      p = *( myset.begin() ) ;
            visited[p.second] = true ;



            for( vector< pii>::iterator it = graph[p.second].begin() ; it != graph[p.second].end() ; it++ ) {
                if( !visited[(*it).second] && ( dist[p.second] + (*it).first ) < dist[(*it).second] ) {
                    myset.erase(make_pair(dist[(*it).second],(*it).second ) );
                    dist[(*it).second] =  dist[p.second] + (*it).first  ;
                    myset.insert(make_pair(dist[(*it).second],(*it).second ) ) ;
                    path[(*it).second] = p.second ;
                }
            }
            myset.erase(p) ;

    }
}


int main() {

  cout.sync_with_stdio(0) ;
  int t , v , k ;
  long long int a, b , c ;

   #ifndef ONLINE_JUDGE
        freopen( "in.txt" , "r" , stdin ) ;
        freopen( "out.txt" , "w" , stdout ) ;
    #endif // ONLINE_JUDGE

    cin >> t ;
   while( t-- ) {


    cin >> v >> k ;

        long long int total = 0 ;
    for( int i = 0 ; i <= v ; i++ ) graph[i].clear() ;//graph cleared...
    for( int i = 0 ; i < k ; i++  ) {
      cin >> a >> b >> c ;
      p.first = c ; p.second = b ;
      graph[a].push_back(p) ;
      p.second = a ;
      graph[b].push_back(p) ;
    }

        cin >> a >> b >> c ;//path from a to c via b needs to be calculated....

    dijikstra(b,c,v) ;
    total += dist[c] ;

        //cout << "executed algo : " << endl ;
        stack<int> my_stack ;
        if( dist[c] == MAX ) { cout << "No Train Found." << endl ;  }
        else {
            int j = path[c] ;
            my_stack.push( c ) ;
            while( 1 ) {
                my_stack.push( j ) ;
                if( j == b ) break ;
                j = path[j] ;
            }

            /*while( !my_stack.empty() ) {
            cout << my_stack.top() << ' ' ;
            my_stack.pop() ;

            }
            */
            my_stack.pop() ; //b is popped otherwise it will appear double in stack ...

            dijikstra(a,b,v) ;
            total += dist[b] ;

        //cout << "executed algo : " << endl ;

        if( dist[b] == MAX ) { cout << "No Train Found." << endl ;  }
        else {
                cout << total << endl ;
            int j = path[b] ;
            my_stack.push( b ) ;
            while( 1 ) {
                my_stack.push( j ) ;
                if( j == a ) break ;
                j = path[j] ;
            }

            while( !my_stack.empty() ) {
            cout << my_stack.top() << ' ' ;
            my_stack.pop() ;

            }
            cout << endl ;

        }

        }



  }

  return 0 ;
}

Second solution

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100005
#define pii pair< long long int,long long  int >
#define pb(x) push_back(x)
long long int INF=1000000000000000;
struct comp {
    bool operator() (const pii &a, const pii &b) {
        return a.second > b.second;
    }
};
priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
long long int D[MAX];
bool F[MAX];
int Path[MAX];
vector<int> p;
vector<int> p1;
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        long long int Dist=0;
        int i, u, v, w, sz, nodes, edges, starting;
        // create graph
        scanf("%d %d", &nodes, &edges);
        for(i=0; i<edges; i++) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].pb(pii(v, w));
            G[v].pb(pii(u, w)); // for undirected
        }
        int A,B,C;
        scanf("%d%d%d", &A,&B,&C);
        // initialize graph
        /*
        From A to B
        */
        for(i=1; i<=nodes; i++){ 
            D[i] = INF;
            F[i]=false;
        }
        D[A] = 0;
        Q.push(pii(A, 0));

        // dijkstra
        while(!Q.empty()) {
            u = Q.top().first;
            Q.pop();
            if(F[u]) continue;
            sz = G[u].size();
            for(i=0; i<sz; i++) {
                v = G[u][i].first;
                w = G[u][i].second;
                if(!F[v] && D[u]+w < D[v]) {
                    D[v] = D[u] + w;
                    Path[v]=u;
                    //printf("%d %d-->n",v,u);
                    Q.push(pii(v, D[v]));
                }
            }
            F[u] = 1; // done with u
        }
        //IF distance from A to B is INF
        if(D[B]==INF)
        {
            printf("No Train Found.n");
            goto end;
        }
        else
        {
            Dist+=D[B];
            //Restore path
            for (int v=B; v!=A;v=Path[v])
            {
                p.push_back(v);
            }
            p.push_back(A);
        }
        // result
        //for(i=1;i<=nodes; i++) printf("Node %d, min weight = %lldn", i, D[i]);
        /*
        From B to C
        */
        Q=priority_queue< pii, vector< pii >, comp > ();
        for(i=1; i<=nodes; i++)
        { 
            D[i] = INF;
            F[i]=false;
        }
        D[B] = 0;
        Q.push(pii(B, 0));
        // dijkstra
        while(!Q.empty()) 
        {
            u = Q.top().first;
            Q.pop();
            if(F[u]) continue;
            sz = G[u].size();
            for(i=0; i<sz; i++) 
            {
                v = G[u][i].first;
                w = G[u][i].second;
                if(!F[v] && D[u]+w < D[v]) {
                    D[v] = D[u] + w;
                    Path[v]=u;
                    Q.push(pii(v, D[v]));
                }
            }
            F[u] = 1; // done with u
        }    

        //Check there is path or not
        if(D[C]==INF)
        {
            printf("No Train Found.n");
            goto end;
        }
        else
        {
            Dist+=D[C];
            printf("%lldn",Dist);
            for(i=p.size()-1;i>=0;i--)
                printf("%d ",p[i]);
            p.clear();
            for (int v=C; v!=B; v=Path[v])
                p.push_back(v);
            for(i=p.size()-1;i>=0;i--)
                printf("%d ",p[i]);    
            printf("n");          
        }
        end:
        //Clear Graph
        p.clear();
        for(i=0;i<MAX;i++)
            G[i].clear();
        Q=priority_queue< pii, vector< pii >, comp > ();

    }
    return 0;
}

coding problems