Code for question: There is a source (S) and destination (D) and a spacecraft has to go from S to D. There are N number of wormholes in between which has following properties: Each wormhole has an entry and an exit. Each wormhole is bi-directional i.e. one can enter and exit from any of the ends. The time to cross the wormhole is given and the s…

wormhole_samsung.cpp

#include<iostream>
using namespace std;
#define i_max 2147483647
int nw,sx,sy,dx,dy;//Source and destination co-ordinates
int dist[1001][1001];
bool set[1001][1001];
class Wormhole{
	public:
		int x1,y1,x2,y2,cost;
		
		void get(){
			cin >> x1 >> y1 >> x2 >> y2 >> cost;
		}
};
Wormhole A[10];
int row_mov[] = {1,-1,0,0};
int col_mov[] = {0,0,1,-1}; 


void initializeArrays(int m,int n){
	//Filling array with 1s
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			dist[i][j] = i_max;
			set[i][j] = false;
		}
	}
}

void setMinRowCol(int &row,int &col){
	int min_dist=i_max,min_i=-1,min_j=-1;
	for(int i=1;i<=dx;i++){
		for(int j=1;j<=dy;j++){
			if(!set[i][j] && dist[i][j]<min_dist){
				min_dist = dist[i][j];
				min_i = i;
				min_j = j;
			}
		}
	}
	row = min_i;
	col = min_j;
}

int wormentry(int i,int j)
{
    for(int k=0;k<nw;k++)
    {
        if(A[k].x1==i && A[k].y1==j)
            return k;
    }
    return -1;
}

int wormexit(int i,int j)
{
    for(int k=0;k<nw;k++)
    {
        if(A[k].x2==i && A[k].y2==j)
            return k;
    }
    return -1;
}

bool isValid(int i,int j){
	if(i<1 || j<1 || i>dx || j>dy){
		return false;
	}
	return true;
}

int findMinCost(){
	initializeArrays(dx+1,dy+1);
	//Run dijkstra
	dist[sx][sy] = 0;//Distance from source to source is 0
	//set[sx][sy] = true;//We have reached source
	
	for(int i=1;i<=dx*dy;i++){
		int row=-1,col=-1;
		setMinRowCol(row,col);//Find min row,col that are unset and proceed with min_dist path
		
		if(row == -1 && col == -1){//If not found then break
			break;
		}
		if(row == dx && col == dy){//If we've reached destination, return the cost
			return dist[row][col];
		}
		
		set[row][col] = true;//Set the current row,col
		
		for(int j=0;j<4;j++)//Move in all 4 directions
        {
            int x = row + row_mov[j];
            int y = col + col_mov[j];

            if(isValid(x,y) && !set[x][y] && dist[x][y]>dist[row][col]+1)
                dist[x][y] = dist[row][col] + 1;
        }
        
        int w_entry = wormentry(row,col);//If worm entry is at row,col ,i.e., row = x1 & col = y1 then exit is at x2,y2
        if(w_entry!=-1)
        {
            int x = A[w_entry].x2;
            int y = A[w_entry].y2;

            if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_entry].cost) //If cost of wormhole is minimum go through the wormhole
                dist[x][y] = dist[row][col]+A[w_entry].cost;
        }
        int w_exit = wormexit(row,col);//If worm exit is at row,col ,i.e., row = x2 & col = y2 then entry is at x1,y1
        if(w_exit!=-1)
        {
            int x = A[w_exit].x1;
            int y = A[w_exit].y1;

            if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_exit].cost) //If cost of wormhole is minimum go through the wormhole
                dist[x][y] = dist[row][col]+A[w_exit].cost;
        }
	}
	return -1;
}

int main(){
	cin >> sx >> sy >> dx >> dy;//Scanning source and destination
	
	cin >> nw;//No of wormholes
	
	//Scanning wormholes info
	for(int i=0;i<nw;i++){
		A[i].get();
	}
	
	cout << findMinCost();
	return 0;
}

#include<iostream> using namespace std; #define i_max 214748364 int nw,sx,sy,dx,dy;//Source and destination co-ordinates int dist[1001][1001]; bool set[1001][1001]; class Wormhole{ public: int x1,y1,x2,y2,cost; void get(){ cin >> x1 >> y1 >> x2 >> y2 >> cost; } }; Wormhole A[10]; int row_mov[] = {-1,0,0,1}; int col_mov[] = {0,-1,1,0}; void initializeArrays(int m,int n){ //Filling array with 1s for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dist[i][j] = i_max; set[i][j] = false; } } } void setMinRowCol(int &row,int &col){ int min_dist=i_max,min_i=-1,min_j=-1; for(int i=0;i<=180;i++){ for(int j=0;j<=180;j++){ if(!set[i][j] && dist[i][j]<min_dist){ min_dist = dist[i][j]; min_i = i; min_j = j; } } } row = min_i; col = min_j; } int wormentry(int i,int j) { for(int k=0;k<nw;k++) { if(A[k].x1==i && A[k].y1==j) return k; } return -1; } int wormexit(int i,int j) { for(int k=0;k<nw;k++) { if(A[k].x2==i && A[k].y2==j) return k; } return -1; } bool isValid(int i,int j){ if(i<0 || j<0 || i>180 || j>180){ return false; } return true; } int findMinCost(){ initializeArrays(181,181); //Run dijkstra dist[sx][sy] = 0;//Distance from source to source is 0 //set[sx][sy] = true;//We have reached source for(int i=1;i<=(181)*(181);i++){ //cout<<i; int row=-1,col=-1; setMinRowCol(row,col);//Find min row,col that are unset and proceed with min_dist path if(row == -1 && col == -1){//If not found then break break; } set[row][col] = true;//Set the current row,col for(int j=0;j<4;j++)//Move in all 4 directions { int x = row + row_mov[j]; int y = col + col_mov[j]; if(isValid(x,y) && !set[x][y] && dist[x][y]>dist[row][col]+1) { dist[x][y] = dist[row][col] + 1; // if(x>90)cout<<dist[x][y]<<" "<<x<<y<<" "; } } int w_entry = wormentry(row,col);//If worm entry is at row,col ,i.e., row = x1 & col = y1 then exit is at x2,y2 if(w_entry!=-1) { int x = A[w_entry].x2; int y = A[w_entry].y2; if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_entry].cost) //If cost of wormhole is minimum go through the wormhole dist[x][y] = dist[row][col]+A[w_entry].cost; } int w_exit = wormexit(row,col);//If worm exit is at row,col ,i.e., row = x2 & col = y2 then entry is at x1,y1 if(w_exit!=-1) { int x = A[w_exit].x1; int y = A[w_exit].y1; if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_exit].cost) //If cost of wormhole is minimum go through the wormhole dist[x][y] = dist[row][col]+A[w_exit].cost; } } //If we've reached destination, return the cost return dist[dx][dy]; } int main(){ cin >> sx >> sy >> dx >> dy;//Scanning source and destination cin >> nw;//No of wormholes //Scanning wormholes info for(int i=0;i<nw;i++){ A[i].get(); } cout << findMinCost(); return 0; }. I used 181*181 because in my case there is a exit of warm hole at 120,180 so you have to take the maximum coordinate of input let say x,y then it will be 1to x+1*y+1 please take care of that .

…

On Fri, Oct 11, 2019, 5:15 PM AASHI BHATIA ***@***.***> wrote: Ill send you my whole code On Fri, Oct 11, 2019, 10:52 AM fuloriyaChetan ***@***.***> wrote: > In this solution can you tell me how to take input for wormhole > coordinates?? . Please let me know. > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <https://gist.github.com/b58c38b3556271059182244676ba06a1?email_source=notifications&email_token=AHKF2UJKNPIDFRGLG5M4Q2LQOAERXA5CNFSM4I6WJ5F2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2JSQ#gistcomment-3052328>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AHKF2UM7WLX2UZ3KAZM7RTDQOAERXANCNFSM4I6WJ5FQ> > . >

Your code was absolutely fine it just that in for loop you have to start from zero because your array index can zero for source

…

On Fri, Oct 11, 2019, 5:20 PM AASHI BHATIA ***@***.***> wrote: #include<iostream> using namespace std; #define i_max 214748364 int nw,sx,sy,dx,dy;//Source and destination co-ordinates int dist[1001][1001]; bool set[1001][1001]; class Wormhole{ public: int x1,y1,x2,y2,cost; void get(){ cin >> x1 >> y1 >> x2 >> y2 >> cost; } }; Wormhole A[10]; int row_mov[] = {-1,0,0,1}; int col_mov[] = {0,-1,1,0}; void initializeArrays(int m,int n){ //Filling array with 1s for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dist[i][j] = i_max; set[i][j] = false; } } } void setMinRowCol(int &row,int &col){ int min_dist=i_max,min_i=-1,min_j=-1; for(int i=0;i<=180;i++){ for(int j=0;j<=180;j++){ if(!set[i][j] && dist[i][j]<min_dist){ min_dist = dist[i][j]; min_i = i; min_j = j; } } } row = min_i; col = min_j; } int wormentry(int i,int j) { for(int k=0;k<nw;k++) { if(A[k].x1==i && A[k].y1==j) return k; } return -1; } int wormexit(int i,int j) { for(int k=0;k<nw;k++) { if(A[k].x2==i && A[k].y2==j) return k; } return -1; } bool isValid(int i,int j){ if(i<0 || j<0 || i>180 || j>180){ return false; } return true; } int findMinCost(){ initializeArrays(181,181); //Run dijkstra dist[sx][sy] = 0;//Distance from source to source is 0 //set[sx][sy] = true;//We have reached source for(int i=1;i<=(181)*(181);i++){ //cout<<i; int row=-1,col=-1; setMinRowCol(row,col);//Find min row,col that are unset and proceed with min_dist path if(row == -1 && col == -1){//If not found then break break; } set[row][col] = true;//Set the current row,col for(int j=0;j<4;j++)//Move in all 4 directions { int x = row + row_mov[j]; int y = col + col_mov[j]; if(isValid(x,y) && !set[x][y] && dist[x][y]>dist[row][col]+1) { dist[x][y] = dist[row][col] + 1; // if(x>90)cout<<dist[x][y]<<" "<<x<<y<<" "; } } int w_entry = wormentry(row,col);//If worm entry is at row,col ,i.e., row = x1 & col = y1 then exit is at x2,y2 if(w_entry!=-1) { int x = A[w_entry].x2; int y = A[w_entry].y2; if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_entry].cost) //If cost of wormhole is minimum go through the wormhole dist[x][y] = dist[row][col]+A[w_entry].cost; } int w_exit = wormexit(row,col);//If worm exit is at row,col ,i.e., row = x2 & col = y2 then entry is at x1,y1 if(w_exit!=-1) { int x = A[w_exit].x1; int y = A[w_exit].y1; if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_exit].cost) //If cost of wormhole is minimum go through the wormhole dist[x][y] = dist[row][col]+A[w_exit].cost; } } //If we've reached destination, return the cost return dist[dx][dy]; } int main(){ cin >> sx >> sy >> dx >> dy;//Scanning source and destination cin >> nw;//No of wormholes //Scanning wormholes info for(int i=0;i<nw;i++){ A[i].get(); } cout << findMinCost(); return 0; }. I used 181*181 because in my case there is a exit of warm hole at 120,180 so you have to take the maximum coordinate of input let say x,y then it will be 1to x+1*y+1 please take care of that . On Fri, Oct 11, 2019, 5:15 PM AASHI BHATIA ***@***.***> wrote: > Ill send you my whole code > > On Fri, Oct 11, 2019, 10:52 AM fuloriyaChetan ***@***.***> > wrote: > >> In this solution can you tell me how to take input for wormhole >> coordinates?? . Please let me know. >> >> — >> You are receiving this because you commented. >> Reply to this email directly, view it on GitHub >> <https://gist.github.com/b58c38b3556271059182244676ba06a1?email_source=notifications&email_token=AHKF2UJKNPIDFRGLG5M4Q2LQOAERXA5CNFSM4I6WJ5F2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2JSQ#gistcomment-3052328>, >> or unsubscribe >> <https://github.com/notifications/unsubscribe-auth/AHKF2UM7WLX2UZ3KAZM7RTDQOAERXANCNFSM4I6WJ5FQ> >> . >> >