HackerRank Floyd: City of Blinding Lights problem solution

In this HackerRank Floyd: City of Blinding Lights problem solution, we have 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.

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.

HackerRank Floyd: City of Blinding Lights 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:
        questions_dict[fr].add(to)
answers = dict()
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
                    next_visited.add(node2)
        visited = next_visited
    for to in tos:
        answers[(fr,to)] = dists[to]
for fr, to in questions:
    print(answers[(fr,to)])

Floyd: City of Blinding Lights problem solution in Java.

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

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		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 {
		StringTokenizer tok = new StringTokenizer(in.readLine());
		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];
					}
				}
			}
		}

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

	private static int[][] readGraph(BufferedReader in, int n, int m)
			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++) {
			StringTokenizer tok = new StringTokenizer(in.readLine());

			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;
	}

}

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';
  });
}

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 + %un", 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 -> %dn", a, b);
        printf("%dn", dist[a-1][b-1]);
    }
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}