In this HackerRank Hacker Country problem solution, There are N cities in Hacker Country. Each pair of cities are directly connected by a unique directed road, and each road has its own toll that must be paid every time it is used. You're planning a road trip in Hacker Country, and its itinerary must satisfy the following conditions:

1. You can start in any city.
2. You must use 2 or more different roads (meaning you will visit 2 or more cities).
3. At the end of your trip, you should be back in your city of origin.
4. The average cost (sum of tolls paid per road traveled) should be minimum.

Can you calculate the minimum average cost of a trip in Hacker Country?

## Problem solution in Python.

```#!/bin/python3

import os
import sys

def hackerCountry(tolls):
lc = len(tolls)
k = [i for i in range(lc)]

class Hiker:
def __init__(self, tolls: list):
self.cities = tolls
self.min_p = [200,1]
self.min_ratio = self.min_p[0]/self.min_p[1]
self.valid_paths = {}
self.time_in_copy_1 = 0
self.time_in_copy_2 = 0
self.time_in_copy_3 = 0
self.best_path = []
self.it = range(lc)
self.it2 = [x for x in ["road","toll","is_over"]]
self.iterations = 0
self.possible_paths = []
def find_start_path_for_city(self, city: int):
self.valid_paths[city] = []
for i, c in enumerate(self.cities[city]):
# print(i,c,city)
path = {"toll": 0, "road": 0, "path": [city], "is_over": False, "lookup":{}}
if i != city:
# path.increase(self.cities[city][c],c)
path["path"].append(i)
path["toll"] += c
path["lookup"][i]=""

self.valid_paths[city].append(path)
# find return path
if (path["toll"] + self.cities[i][city]) / (
self.min_p[0] = path["toll"] + self.cities[i][city]
self.min_ratio = self.min_p[0] / self.min_p[1]

def expand_path(self, path: dict,city:int,):
if path["toll"] / path["road"] > self.min_ratio:
path["is_over"] = True
while not path["is_over"]:
#pp = self.get_path(path)
pp = path["path"]
start_len = len(pp)
for c in self.it:
if c not in path["lookup"]:

t= self.cities[pp[-1]][c]
path["toll"] += t
pp.append(c)
if path["toll"] / path["road"] < self.min_ratio:
cities_left = list(set(pp[1:] + k))
tolls_left = [self.cities[c][_] for _ in
cities_left]
if (min(tolls_left) + path["toll"]) / (path["road"] + 1) < self.min_ratio:

path_new = {x: path[x] for x in self.it2}
path_new["path"]=pp.copy()
path_new["lookup"]=path["lookup"].copy()
path_new["lookup"][c]=""
self.valid_paths[city].append(path_new)
if (path["toll"] + self.cities[c][city]) / (
self.min_p[0] = path["toll"] + \
self.cities[c][
city]
self.min_ratio = self.min_p[0]/self.min_p[1]

path["toll"]-=t
pp.pop(-1)
if len(pp) == start_len:
path["is_over"] = True

def check_paths_for_city(self, city: int):
finalized_paths = 0
while finalized_paths < len(self.valid_paths[city]):
finalized_paths = 0
for i, p in enumerate(self.valid_paths[city]):
if p["is_over"]:
finalized_paths += 1
else:
self.expand_path(p,city)

def find_best_ratio(self, a: int, b: int):
# print(f"original res {a}/{b}")
y = 10
while True:
to_break = True
for i in range(y, 1, -1):
if a % i == 0 and b % i == 0:
a = a // i
b = b // i
y = i
to_break = False
if to_break:
break
return (f"{a}/{b}")

def main(self):
for c in self.it:
self.find_start_path_for_city(c)
for c in self.it:
self.check_paths_for_city(c)
return self.find_best_ratio(self.min_p[0], self.min_p[1])

h = Hiker(tolls)
return h.main()

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

n = int(input())

tolls = []

for _ in range(n):
tolls.append(list(map(int, input().rstrip().split())))

result = hackerCountry(tolls)

fptr.write(result + '\n')

fptr.close()
```

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

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

private static final Scanner scan = new Scanner(System.in);

public static void main(String[] args) throws IOException {

int n = scan.nextInt();
int[][] ar = new int[n][n];
int p = 6;
int[][][] mat = new int[p][n][n];

for (int i=0; i < n; i++) {
for (int j = 0; j < n; j++) {
int s = scan.nextInt();
if(s == 0) {
ar[i][j] = 1000000;
} else {
ar[i][j] = s;
}
}
}

scan.close();

for (int i = 0; i < p; i++) {
if (i >= n) {
break;
}

for (int j = 0; j < n; j++) {
mat[i][0][j] = ar[i][j];
}
}

for (int i = 0; i < p; i++){
if (i >= n) {
break;
}
if (i == 4) {
continue;
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n; k++){
int mini = 1000000;
for (int s = 0; s < n; s++) {
int temp = mat[i][j-1][s] + ar[s][k];
if (temp < mini) mini = temp;
}
mat[i][j][k] = mini;
}
}
}

double min = 1000000;
int a = 0, b = 0;
for(int i = 0; i < p; i++) {
if (i >= n) {
break;
}
if (i == 4) {
continue;
}
for (int j = 0; j < n; j++) {
double s = ((double) mat[i][j][i]) / (j + 1);
if (s < min) {
min = s;
a = mat[i][j][i];
b = j + 1;
}
}
}
BigInteger w = new BigInteger("" + a);
BigInteger q = new BigInteger("" + b);
int gcd = (w.gcd(q)).intValue();

System.out.println((a / gcd)+"/"+(b / gcd));
}
}
```

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

## Problem solution in C++.

```#include <iostream>
#include <map>

#define INFINITY 0x3f3f3f3f
#define MAXN 505
using namespace std;

typedef long long LL;

LL get_difference(pair<int, int> a, pair<int, int> b) {
LL t = (LL)a.first * b.second - (LL)a.second * b.first;
return t;
}

int get_GCD(int a, int b) {
return b == 0 ? a : get_GCD(b, a % b);
}

void get_min_cost(pair<int, int> p) {
int g = get_GCD(p.first, p.second);
cout << p.first / g << "/" << p.second / g << endl;
}

int main() {

cin >> input;
for (int i = 0; i < input; i++) {
for (int j = 0; j < input; j++) {

if (i == j)
}
}

for (int i = 0; i <= input + 1; i++) {
for (int j = 0; j < input + 1; j++) {
cities[i][j] = INFINITY;
}
}

s = input++;

for (int i = 0; i < input - 1; i++) {
}

cities[0][s] = 0;

for (int k = 0; k < input; k++) {
for (int i = 0; i < input; i++) {
for (int j = 0; j < input; j++) {
if (cities[k][i] + roads[i][j] < cities[k + 1][j]) {
cities[k + 1][j] = cities[k][i] + roads[i][j];
}
}
}
}

directions = make_pair(INFINITY, 1);

for(int i = 0; i < input - 1; i++) {
if(cities[input][i] == INFINITY) continue;

for(int k = 0; k < input - 1; k++) {
if(get_difference(make_pair(cities[input][i] - cities[k][i], input - k), max_roads) > 0)
max_roads = make_pair(cities[input][i] - cities[k][i], input - k);
}

}

get_min_cost(directions);

return 0;
}```

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

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
long long CC(long long n, long long d);
int a[500][500],dp[501][500];

int main(){
int N,i,j,k,p,q,tp,tq,t;
long double ans=201,tans;
scanf("%d",&N);
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&a[i][j]);
for(i=0;i<=N;i++)
for(j=0;j<N;j++)
if(!i)
dp[i][j]=0;
else
for(k=0,dp[i][j]=100000;k<N;k++){
if(j==k)
continue;
if(dp[i-1][k]+a[k][j]<dp[i][j])
dp[i][j]=dp[i-1][k]+a[k][j];
}
for(i=0;i<N;i++){
for(tans=j=0;j<N;j++)
if((dp[N][i]-dp[j][i])/(long double)(N-j)>tans){
tans=(dp[N][i]-dp[j][i])/(long double)(N-j);
tp=dp[N][i]-dp[j][i];
tq=N-j;
}
if(tans<ans){
ans=tans;
p=tp;
q=tq;
}
}
t=CC(p,q);
printf("%d/%d",p/t,q/t);
return 0;
}
long long CC(long long n, long long d){
while( 1 )
{
n = n % d;
if( n == 0 )
return d;
d = d % n;
if( d == 0 )
return n;
}
}
```

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