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.

HackerRank Floyd: City of Blinding Lights problem solution


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)])

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

}

{"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}