Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Floyd : City of Blinding Lights Problem Solution

HackerRank Floyd : City of Blinding Lights Solution

Posted on May 20, 2023May 20, 2023 By Yashwant Parihar No Comments on HackerRank Floyd : City of Blinding Lights Solution

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:

  1. 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.
  1. There is no path from 2 to 5, so we return -1.
  2. 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 4

Sample Output

5
-1
11
HackerRank Floyd : City of Blinding Lights Problem Solution
HackerRank Floyd : City of Blinding Lights Problem Solution

Table of Contents

  • Floyd : City of Blinding Lights C Solution
  • Floyd : City of Blinding Lights C++ Solution
  • Floyd : City of Blinding Lights C Sharp Solution
  • Floyd : City of Blinding Lights Java Solution
  • Floyd : City of Blinding Lights JavaScript Solution
  • Floyd : City of Blinding Lights Python Solution

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)
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Jeanie’s Route Problem Solution
Next Post: HackerRank Roads in HackerLand Solution

Related Posts

HackerRank The Longest Common Subsequence Problem Solution HackerRank The Longest Common Subsequence c
HackerRank Minimum Absolute Difference in an Array Problem Solution HackerRank Minimum Absolute Difference in an Array c
HackerRank Find the Median Problem Solution HackerRank Find the Median Problem Solution c
HackerRank Marc's Cakewalk Problem Solution HackerRank Marc’s Cakewalk Problem Solution c
HackerRank ACM ICPC Team Problem Solution HackerRank ACM ICPC Team Problem Solution c
HackerRank Road Network Problem Solution HackerRank Road Network Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme