# HackerRank Floyd: City of Blinding Lights problem solution

In this 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.

## Problem solution in Python.

```n, m = tuple(int(x) for x in input().strip().split())
edges = {node: list() for node in range(1,n+1)}
for _ in range(m):
f,t,r = tuple(int(x) for x in input().strip().split())
try:
idx = next(i for i,(to,_) in enumerate(edges[f]) if to == t)
edges[f][idx] = (t,r)
except StopIteration:
edges[f].append((t,r))
questions = [
tuple(int(x) for x in input().strip().split())
for _ in range(int(input()))
]
questions_dict = dict()
for fr, to in questions:
if fr not in questions_dict:
questions_dict[fr] = {to}
else:
for fr, tos in questions_dict.items():
visited = {fr}
dists = {node: -1 for node in range(1,n+1)}
dists[fr] = 0
while visited:
next_visited = set()
for node in visited:
nd = dists[node]
for node2,r in edges[node]:
nw = nd+r
if dists[node2] == -1 or nw < dists[node2]:
dists[node2] = nw
visited = next_visited
for to in tos:
for fr, to in questions:

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
// StringTokenizer tok = new StringTokenizer(in.readLine());
int t = 1;
for (int i = 0; i < t; i++) {
oneTest(in);
}

}

private static void oneTest(BufferedReader in) throws IOException {
int n = Integer.parseInt(tok.nextToken());
int m = Integer.parseInt(tok.nextToken());

int[][] graph = readGraph(in, n, m);
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][k] == -1 || graph[k][j] == -1)
continue;
if (graph[i][j] == -1
|| graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}

for (int i = 0; i < q; i++) {
int a = Integer.parseInt(tok.nextToken()) - 1;
int b = Integer.parseInt(tok.nextToken()) - 1;
System.out.println(graph[a][b]);
}
}

throws IOException {
int[][] res = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(res[i], -1);
res[i][i] = 0;
}
for (int i = 0; i < m; i++) {

int a = Integer.parseInt(tok.nextToken()) - 1;
int b = Integer.parseInt(tok.nextToken()) - 1;
int w = Integer.parseInt(tok.nextToken());

res[a][b] = w;

}
return res;
}

}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <limits>
#include <list>
#include <iostream>
#include <queue>
#include <vector>
#include <cstddef>
using namespace std;

// Support code

template <typename T>
T input(std::istream &is = std::cin) {
T value;
is >> value;
return value;
}

template <typename Function>
void repeat(std::size_t n, Function f) {
while (n--)
f();
}

template <typename T>
class matrix {
public:
using index_type = std::pair<size_t, size_t>;
using reference = typename std::vector<T>::reference;
using const_reference = typename std::vector<T>::const_reference;

matrix(index_type bounds) : bounds_(bounds), data_(rows() * cols()) {}

matrix(index_type bounds, const T &value)
: bounds_(bounds), data_(rows() * cols(), value) {}

size_t pos(index_type idx) const { return idx.first * cols() + idx.second; }
size_t rows() const { return bounds_.first; }
size_t cols() const { return bounds_.second; }
reference operator[](index_type idx) { return data_[pos(idx)]; }
const_reference operator[](index_type idx) const { return data_[pos(idx)]; }

private:
index_type bounds_;
std::vector<T> data_;
};

template <typename T>
static void minimize(T &elem, const T &value) {
if (elem > value)
elem = value;
}

int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

const auto num_vertices = input<size_t>();
const auto num_edges = input<size_t>();

constexpr auto inf = std::numeric_limits<size_t>::max();
matrix<size_t> dist({num_vertices, num_vertices}, inf);

for (size_t v = 0; v != num_vertices; ++v)
dist[{v, v}] = 0;

repeat(num_edges, [&dist] {
const auto source = input<size_t>() - 1;
const auto target = input<size_t>() - 1;
const auto weight = input<unsigned long>();
dist[{source, target}] = weight;
});

for (size_t k = 0; k != num_vertices; ++k) {
for (size_t i = 0; i != num_vertices; ++i) {
for (size_t j = 0; j != num_vertices; ++j) {
const auto &dist_ik = dist[{i, k}];
const auto &dist_kj = dist[{k, j}];
if (dist_ik == inf || dist_kj == inf)
continue;

minimize(dist[{i, j}], dist_ik + dist_kj);
}
}
}

repeat(input<size_t>(), [&dist] {
const auto source = input<size_t>() - 1;
const auto target = input<size_t>() - 1;
std::cout << static_cast<long>(dist[{source, target}]) << '\n';
});
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

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

#define d(...) // fprintf(stderr, __VA_ARGS__)

int main() {
int nv, ne;
scanf("%d %d", &nv, &ne);
unsigned dist[nv][nv];
memset(dist, 0xff, sizeof(unsigned) * nv * nv);
for (int k = 0; k != nv; ++k) {
dist[k][k] = 0;
}
while (ne--) {
int a,b,w;
scanf("%d %d %d", &a, &b, &w);
dist[a-1][b-1] = w;
}
for (int k = 0; k != nv; ++k) {
for (int i = 0; i != nv; ++i) {
for (int j = 0; j != nv; ++j) {
if (dist[i][j] > (long) dist[i][k] + dist[k][j]) {
d("%u > %u + %u\n", dist[i][j], dist[i][k], dist[k][j]);
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int nq;
scanf("%d", &nq);
while (nq--) {
int a,b;
scanf("%d %d", &a, &b);
d("Query %d -> %d\n", a, b);
printf("%d\n", dist[a-1][b-1]);
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
```

{"mode":"full","isActive":false}