HackerEarth IRCTC problem solution YASH PAL, 31 July 2024 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 = %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