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:
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)])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 + %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;
}
0 Comments