In this post, we will solve HackerRank Floyd : City of Blinding Lights Problem Solution.
Given a directed weighted graph where weight indicates distance, for each query, determine the length of the shortest path between nodes. There may be many queries, so efficiency counts.
For example, your graph consists of 5 nodes as in the following:
- There are two paths from 4 to 3:
- 4 1 2 3 at a distance of 4+ 5+1=10
4 153 at a distance of 4+3+2=9 In this case we choose path 2.
- There is no path from 2 to 5, so we return -1.
- There is one path from 5 to 3:
5 – 3 at a distance of 2.
Input Format
The first line has two integers n and m, the number of nodes and the number of edges in
the graph.
Each of the next m lines contains three space-separated integers u v and w, the two nodes between which the directed edge u⇒ v exists, and w, the length of the edge.
The next line contains a single integer q, the number of queries.
Each of the next q lines contains two space-separated integers a and b, denoting the start and end nodes for traversal.
The distance from a node to itself is always 0 and it is always reachable from itself.
If there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.
Output Format
Print q lines, each containing a single integer specifying the shortest distance for the query.
If the destination node is not reachable, return -1
Sample Input
STDIN Function
----- --------
4 5 n = 4, m = 5
1 2 5 u = 1, v = 2, w = 5
1 4 24 u = 1, v =4, w = 24 ...
2 4 6
3 4 4
3 2 7
3 q = 3
1 2 query 0: from 1 to 2
3 1 query 1: from 3 to 1
1 4 query 2: from 1 to 4Sample Output
5
-1
11
Floyd : City of Blinding Lights C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define INTMAX 140001
int ADMAT[400][400];
int main() {
int V=0,E=0;
int i=0,j=0,k=0;
int p=0,q=0,r=0;
scanf("%d%d",&V,&E);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
{
ADMAT[i][j]=INTMAX;
if(i==j)
ADMAT[i][j]=0;
}
}
for(i=0;i<E;i++)
{
scanf("%d%d%d",&p,&q,&r);
ADMAT[p-1][q-1]=r;
}
for(k=0;k<V;k++)
{
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
{
if(ADMAT[i][j]>ADMAT[i][k]+ADMAT[k][j])
ADMAT[i][j]=ADMAT[i][k]+ADMAT[k][j];
}
}
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&p,&r);
if(ADMAT[p-1][r-1]<INTMAX)
printf("%d\n",ADMAT[p-1][r-1]);
else
printf("-1\n");
}
return 0;
}Floyd : City of Blinding Lights C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> mat(n, vector<int>(n, 1000000));
for (int i = 0; i < m; ++i) {
int a, b, v;
cin >> a >> b >> v;
mat[a-1][b-1] = v;
}
for (int i = 0; i < n; ++i) {
mat[i][i] = 0;
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
}
}
}
int Q;
cin >> Q;
for (int q = 0; q < Q; ++q) {
int a, b;
cin >> a >> b;
if (mat[a-1][b-1] < 1000000) cout << mat[a-1][b-1] << endl;
else cout << -1 << endl;
}
return 0;
}Floyd : City of Blinding Lights C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(string[] args)
{
var line = Console.ReadLine().Split(' ');
var N = Convert.ToInt32(line[0]);
var M = Convert.ToInt32(line[1]);
var graph = new int[N, N];
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
graph[i, j] = int.MaxValue;
}
}
for (var i = 0; i < N; i++)
{
graph[i, i] = 0;
}
for (var i=0; i < M; i++)
{
line = Console.ReadLine().Split(' ');
var x = Convert.ToInt32(line[0]);
var y = Convert.ToInt32(line[1]);
var r = Convert.ToInt32(line[2]);
graph[x - 1, y - 1] = r;
}
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
for (var k = 0; k < N; k++)
{
if (graph[j, k] > (long)graph[j, i] + graph[i, k])
{
graph[j, k] = graph[j, i] + graph[i, k];
}
}
}
}
var Q = Convert.ToInt32(Console.ReadLine());
for (var i=0; i < Q; i++)
{
line = Console.ReadLine().Split(' ');
var a = Convert.ToInt32(line[0]);
var b = Convert.ToInt32(line[1]);
if (graph[a - 1, b - 1] == int.MaxValue)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(graph[a - 1, b -1]);
}
}
}
}Floyd : City of Blinding Lights Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
public class Solution {
private static final long inf = Long.MAX_VALUE;
private static void floyd_warshall(List<Integer> roadFrom, List<Integer> roadTo, List<Integer> roadWeight, List<List<Integer>>queries) {
int n = 0;
for(int i : roadFrom) if(n < i) n = i;
for(int i : roadTo) if(n < i) n = i;
long[][] mat = new long[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
mat[i][j] = inf;
}
}
for(int i = 0; i < roadFrom.size(); i++) {
mat[roadFrom.get(i) - 1][roadTo.get(i) - 1] = roadWeight.get(i);
}
floyd_warshall(mat);
for(List<Integer> q : queries) {
int x = q.get(0);
int y = q.get(1);
if(x == y) {
System.out.println(0);
} else if(mat[x-1][y-1] == inf) {
System.out.println(-1);
} else {
System.out.println(mat[x-1][y-1]);
}
}
}
private static void floyd_warshall(long[][] mat) {
int n = mat.length;
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(mat[i][k] != inf && mat[k][j] != inf) {
mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] roadNodesEdges = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int roadNodes = Integer.parseInt(roadNodesEdges[0]);
int roadEdges = Integer.parseInt(roadNodesEdges[1]);
List<Integer> roadFrom = new ArrayList<>();
List<Integer> roadTo = new ArrayList<>();
List<Integer> roadWeight = new ArrayList<>();
IntStream.range(0, roadEdges).forEach(i -> {
try {
String[] roadFromToWeight = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
roadFrom.add(Integer.parseInt(roadFromToWeight[0]));
roadTo.add(Integer.parseInt(roadFromToWeight[1]));
roadWeight.add(Integer.parseInt(roadFromToWeight[2]));
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
int q = Integer.parseInt(bufferedReader.readLine().trim());
List<List<Integer>> queries = new ArrayList<List<Integer>>();
IntStream.range(0, q).forEach(qItr -> {
try {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
List<Integer> k = new ArrayList<Integer>();
int x = Integer.parseInt(firstMultipleInput[0]);
int y = Integer.parseInt(firstMultipleInput[1]);
k.add(x);
k.add(y);
queries.add(k);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
floyd_warshall(roadFrom, roadTo, roadWeight, queries);
bufferedReader.close();
}
}Floyd : City of Blinding Lights JavaScript Solution
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
let cache = {};
function getMinWeight(x, y, data){
const stack = [];
stack.push(x);
const marks = { [x]: true };
const weightM = { [x]: 0 };
while(!!stack.length){
const param = stack.pop();
if(!data[param]) continue;
const roadToW = data[param].to;
for(const key in roadToW){
if(marks[key]) continue;
if(!weightM[key] || weightM[key] > roadToW[key] + weightM[param]) {
weightM[key] = roadToW[key] + weightM[param]
}
}
let buf = {};
for(const key in weightM){
if(!marks[key] && (!buf.weight || buf.weight > weightM[key])){
buf = { key, weight: weightM[key] };
}
}
if(buf.key == y) break;
stack.push(buf.key);
marks[buf.key] = true;
}
return weightM[y] || -1;
}
function memogetMinWeight(data) {
return (x, y) => {
const key = `${x}_${y}`;
if (key in cache) {
return cache[key];
}
else {
const result = getMinWeight(x, y, data);
cache[key] = result;
return result;
}
}
}
function main() {
const roadNodesEdges = readLine().split(' ');
const roadNodes = parseInt(roadNodesEdges[0], 10);
const roadEdges = parseInt(roadNodesEdges[1], 10);
let roadFrom;
let roadTo;
let roadWeight;
const data = {};
for (let i = 0; i < roadEdges; i++) {
const roadFromToWeight = readLine().split(' ');
roadFrom = parseInt(roadFromToWeight[0], 10);
roadTo = parseInt(roadFromToWeight[1], 10);
roadWeight = parseInt(roadFromToWeight[2], 10);
if(data[roadFrom]){
data[roadFrom].to[roadTo] = roadWeight
}else{
data[roadFrom] = {
to: { [roadTo]: roadWeight},
}
}
}
const q = parseInt(readLine(), 10);
const getMinWeight = memogetMinWeight(data);
let line = '';
for (let qItr = 0; qItr < q; qItr++) {
const xy = readLine().split(' ');
const x = parseInt(xy[0], 10);
const y = parseInt(xy[1], 10);
if(x === y){
line += '0\n';
continue;
}
const result = getMinWeight(x, y);
line += result + '\n';
}
console.log(line);
}Floyd : City of Blinding Lights Python Solution
INF = float('inf')
def solve(v, edges):
sol = { u: INF for u in edges }
sol[v] = 0
unvisited = list(edges)
while unvisited:
cur = min(range(len(unvisited)), key=lambda i: sol[unvisited[i]])
cur = unvisited.pop(cur)
for u in edges[cur]:
new = sol[cur] + edges[cur][u]
if sol[u] == INF or new < sol[u]:
sol[u] = new
return sol
N, M = map(int, input().split())
edges = {v: {} for v in range(1, N + 1)}
for _ in range(M):
X, Y, R = map(int, input().split())
edges[X][Y] = R
solutions = {v: solve(v, edges) for v in edges}
Q = int(input())
for _ in range(Q):
A, B = map(int, input().split())
sol = solutions[A][B]
print(-1 if sol == INF else sol)
