Floyd : City of Blinding Lights – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Floyd : City of Blinding Lights HackerRank Solution
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<iostream>
#include<map>
using namespace std;
#define sd(a) scanf("%d",&a)
#define pd(a) prlong longf("%lld\n",(a))
#define LL long long
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define INF 100000000
int adj[500][500];
int main()
{
int n,m,q,x,y,r,i,j,k;
sd(n);
sd(m);
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
adj[i][j]=INF;
}
adj[i][i]=0;
}
for(i=0;i<m;++i)
{
sd(x);
sd(y);
sd(r);
if(x!=y)
adj[x][y]=r;
}
for(k=1;k<=n;++k)
{
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(adj[i][k]!=INF&&adj[k][j]!=INF)
{
adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]);
}
}
}
}
sd(q);
while(q--)
{
sd(x);
sd(y);
if(adj[x][y]==INF)
printf("%d\n",-1);
else
printf("%d\n",adj[x][y]);
}
}
Java Floyd : City of Blinding Lights HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
String ve = stdIn.nextLine();
String[] tmp = ve.split(" ");
int V = Integer.parseInt(tmp[0]);
int E = Integer.parseInt(tmp[1]);
int[][] graph = new int[V+1][V+1];
for(int i=1;i<=V;i++){
for(int j=1;j<=V;j++){
if(i==j){
graph[i][j] = 0;
}
else{
graph[i][j] = 140000;
}
}
}
for(int i=0;i<E;i++){
String inp_edge = stdIn.nextLine();
String[] temp = inp_edge.split(" ");
int v1 = Integer.parseInt(temp[0]);
int v2 = Integer.parseInt(temp[1]);
int w = Integer.parseInt(temp[2]);
graph[v1][v2] = w;
}
for(int k=1;k<=V;k++){
for(int i=1;i<=V;i++){
for(int j=1;j<=V;j++){
graph[i][j] = Math.min(graph[i][k]+graph[k][j],graph[i][j]);
}
}
}
int Q = stdIn.nextInt();
String buffer = stdIn.nextLine();
for(int i=0;i<Q;i++){
String inp_edge = stdIn.nextLine();
String[] temp = inp_edge.split(" ");
int v1 = Integer.parseInt(temp[0]);
int v2 = Integer.parseInt(temp[1]);
if(graph[v1][v2]>130000)
System.out.println("-1");
else
System.out.println(graph[v1][v2]);
}
}
}
Python 3 Floyd : City of Blinding Lights HackerRank Solution
INFINITY = 0xFFFFFFFF
class vertex:
def __init__(self):
self.adj = {}
def bellman_ford(V, s, sp):
sp[s][s] = 0
sps = sp[s]
for i in range(0,len(V)):
done = True
for x in range(0, len(V)):
for y in V[x].adj.keys():
w = V[x].adj[y]
if sps[y] > sps[x]+w:
sps[y] = sps[x]+w
done = False
if done == True:
break
var = input().split()
N,M = int(var[0]),int(var[1])
SP_done = [INFINITY]*N #Indicates if we have ran SP from a specific source
V = [] #List of vertices
V = [vertex() for i in range(0,N)]
SP = [[INFINITY for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
var = input().split()
x,y,w = int(var[0]), int(var[1]), int(var[2])
x= x-1
y= y-1
V[x].adj[y] = w
T = int(input())
out=""
for t in range(0,T):
var = input().split()
x,y = int(var[0]) , int(var[1])
x = x-1
y = y-1
if SP_done[x] != 0:
SP_done[x] = 0
bellman_ford(V, x, SP)
if SP[x][y] == INFINITY:
out += "{}\n".format(-1)
else:
out += "{}\n".format(SP[x][y])
print(out)
#print(SP)
Python 2 Floyd : City of Blinding Lights HackerRank Solution
import sys
maxx=3000*3000
def dijkstra(dp, neigh, N, s):
global maxx
n=[[maxx,i+1] for i in range(N)]
dist=[[0,0]]+n[:]
dist[s][0]=0
for _ in range(N):
n.sort()
sel=n[0]
del n[0]
for e in neigh[sel[1]]:
dist[e][0]=min(dist[e][0], dist[sel[1]][0]+dp[sel[1]][e])
return dist
def floyd(dp, neigh, rneigh, N):
for k in xrange(1,N+1):
for i in rneigh[k]:
for j in neigh[k]:
m=dp[i][k]+dp[k][j]
if i!=j and dp[i][k]>0 and dp[k][j]>0 and (dp[i][j]==-1 or dp[i][j]>m):
if dp[i][j]==-1:
neigh[i].append(j)
rneigh[j].append(i)
dp[i][j]=m
N,M=sys.stdin.readline().split()
N,M=int(N)+1,int(M)
rng=xrange(N+1)
neigh=[[] for _ in rng]
rneigh=[[] for _ in rng]
dp=[[-1 for x in rng] for x in rng]
for i in xrange(M):
i,j,d=sys.stdin.readline().split()
i,j,d=int(i),int(j),int(d)
dp[i][j]=d
neigh[i].append(j)
rneigh[j].append(i)
if 10*M < N*N:
new=[[]]
for s in range(1, N+1):
new.append([x[0] for x in dijkstra(dp, neigh, N, s)])
dp=new
else:
floyd(dp, neigh, rneigh, N)
sys.stdin.readline()
for s in sys.stdin:
i,j=s.split()
i,j=int(i),int(j)
if i==j: dp[i][j]=0
print dp[i][j]
C Floyd : City of Blinding Lights HackerRank Solution
#include <stdio.h>
#define MAXINT 0xfffffff
void printarr(int vert, int arr[401][401]) {
int i, j;
for (i=1; i <= vert; i++) {
for (j=1; j <= vert; j++) {
printf("%d ",arr[i][j]);
}
printf("\n");
}
return;
}
int main() {
int arr[401][401];
int vert, edges, que;
int from,to, wt;
int i, j, k;
scanf("%d %d", &vert, &edges);
for (i=1; i <= vert; i++) {
for (j=1; j <= vert; j++) {
arr[i][j] = MAXINT;
}
}
for (i=0; i < edges; i++) {
scanf("%d %d %d", &from, &to, &wt);
arr[from][to] = wt;
}
for (k=1; k <= vert; k++) {
for (i=1; i <= vert; i++) {
for (j=1; j <= vert; j++) {
if (arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}
}
scanf("%d", &que);
for (i=0; i < que; i++) {
scanf("%d %d", &from, &to);
if (from == to) {
printf("0\n");
continue;
}
if (arr[from][to] == MAXINT) {
printf("-1\n");
continue;
}
printf("%d\n", arr[from][to]);
}
return 0;
}
Leave a comment below
