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 100000000000000000pii 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 = %lld\n", 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("%lld\n",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;}`