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 = %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;
}
0 Comments