Breadth First Search: Shortest Reach HackerRank Solution C, CPP, Python

We perform the following two queries:

1. The given graph can be represented as:
   where our start node, , is node . The shortest distances from  to the other nodes are one edge to node , one edge to node , and an infinite distance to node  (which it is not connected to). We then return an array of distances from node  to nodes , , and  (respectively): .
2. The given graph can be represented as:

   where our start node, , is node . There is only one edge here, so node  is unreachable from node  and node  has one edge connecting it to node . We then return an array of distances from node  to nodes , and  (respectively): .

Note: Recall that the actual length of each edge is , and we return  as the distance to any node that is unreachable from .

 

Breadth First Search: Shortest Reach HackerRank Solution C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define FROM 0
#define TO 1
#define DISTANCE 0
#define STATUS 1
#define SPENT 0
#define PENDING 1
#define GAP 6

int main() {
    
	int cases, nodes, edges, active, i, origin;
	int node[1000+1][2];		// [node][distance / status]
	int edge[1000*(1000-1)/2+1][2];	// [edge][from node / to node]
	
	scanf("%d", &cases);
	
	while(cases--){
		
		scanf("%d%d", &nodes, &edges);
		
		for(i=1; i <= edges; i++){
			scanf("%d%d", &edge[i][FROM], &edge[i][TO]);
		}
	
		for(i=1; i <= nodes; i++){
			node[i][DISTANCE] = -1;
			node[i][STATUS] = PENDING;
		}
		
		scanf("%d", &origin);
        active = origin;
		node[origin][DISTANCE] = 0;
		unsigned int min;
		while(active){
			
			active = 0;
			min = -1;
			for(i=1; i <= nodes; i++){
				if(node[i][STATUS]==PENDING && node[i][DISTANCE]!=-1 && node[i][DISTANCE]<min){
					min = node[i][DISTANCE];
					active = i;
				}
			}
	
			for(i=1; i<=edges; i++){ //originally thought it was a directed graph :/
				if(edge[i][FROM]==active){
					if(node[edge[i][TO]][DISTANCE]>node[edge[i][FROM]][DISTANCE]+GAP || node[edge[i][TO]][DISTANCE]==-1){
						node[edge[i][TO]][DISTANCE]=node[edge[i][FROM]][DISTANCE]+GAP;
					}
				}
				if(edge[i][TO]==active){
					if(node[edge[i][FROM]][DISTANCE]>node[edge[i][TO]][DISTANCE]+GAP || node[edge[i][FROM]][DISTANCE]==-1){
						node[edge[i][FROM]][DISTANCE]=node[edge[i][TO]][DISTANCE]+GAP;
					}
				}
			}
	
			node[active][STATUS] = SPENT;
	
		}
	
		for(i=1; i<=nodes; i++){
			if(i!=origin)printf("%i ", node[i][DISTANCE]);
		}
	
		printf("\n");
	}
    
    return 0;
}

// some day I'm going to look back on this and want to smack myself

 

Breadth First Search: Shortest Reach HackerRank Solution CPP

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cctype>
#include <limits>
#include <fstream>

using namespace std;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int> > vvi;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define DEC(i,a,b) for(int i=(a); i>=b; --i)
#define FORV(v,i) for(int i=0;i<v.size();++i)
#define FORD(v,i) for(int i=v.size()-1;i>=0;--i)
#define all(c) (c).begin(),(c).end()
#define sz(c) int((c).size())
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007ULL


void bfs(vector<set<int> > &V,int &S,stringstream &ss)
{
	vector<bool> A(V.size(),false);
	vi D(V.size(),-1);
	D[S] = 0;
	queue<int> Q;
	Q.push(S);
	//ss<<"size:"<<V[S].size()<<"\n";
	A[S] = true;
	while(!Q.empty())
	{
		int f = Q.front(); Q.pop();
		//ss<<f<<","<<V[f].size()<<":";
		for(set<int>::iterator it = V[f].begin();
			it != V[f].end() ; ++it)
		{
			int p = *it;
			if(!A[p])
			{
				//ss<<p<<",";
				D[p] = D[f] + 1;
				/*
				int v = D[f] + 1;
				if( v < D[p])
					D[p] = D[f] + 1;
				*/
				A[p] = true;
				Q.push(p);
			}
		}
		//ss<<"\n";
	}
	//ss<<"\n";

	//sort(all(D));
	//int C = 0;
	FORV(D,i)
	{
		if(D[i] == -1)
			ss<<-1<<" ";
		else if(D[i] > 0)
			ss<<(D[i]*6)<<" ";
	}
	ss<<"\n";
	//FOR(i,0,C)
	//	ss<<-1<<" ";
}


int main()
{
	int t;
	ios_base::sync_with_stdio(false);
	cin>>t;
	stringstream ss;
	FOR(i,0,t)
	{
		int n,m;
		cin>>n>>m;
		vector<set<int> > V(n,set<int>());
		FOR(j,0,m)
		{
			int a,b;
			cin>>a>>b;
			a--;
			b--;
			V[a].insert(b);
			V[b].insert(a);
		}
		int S;
		cin>>S;
		S--;
		bfs(V,S,ss);
	}
	cout<<ss.str();
	return 0;
}

 

Breadth First Search: Shortest Reach HackerRank Solution Python

# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys

def solve(n,r,s):
    G=[[] for _ in range(n+1)]
    for [i,j] in r:
        if not((i in G[j]) | (i==j)):
            G[i].append(j)
            G[j].append(i)
    done=[]
    ndone=[s]
    todo=G[s]
    L=[-1 for _ in range(n+1)]
    L[s]=0
    for i in G[s]:
        L[i]=1
    while ndone!=done:
        done=list(ndone)
        ntodo=[]
        for i in todo:
            for j in G[i]:
                if not((j in done) | ((j in ntodo) | (j in todo))):
                    L[j]=L[i]+1
                    ntodo.append(j)
        ndone+=list(todo)
        todo=list(ntodo)
    st=""
    for i in (L[1:s]+L[s+1:]):
        if i!=-1:
            st+=str(6*i)+" "
        else:
            st+=str(i)+" "
    return st





T=int(raw_input())
for _ in range(T):
    [n,m]=map(int,raw_input().strip().split())
    r=[]
    for _ in range(m):
        r.append(map(int,raw_input().strip().split()))
    s=int(raw_input())
    print(solve(n,r,s))