Cerinta completa

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:

  • You can start in any city.
  • You must use or more different roads (meaning you will visit or more cities).
  • At the end of your trip, you should be back in your city of origin.
  • 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?

Time Limits
Time limits for this challenge are provided here.

Input Format

The first line is an integer, (number of cities).
The subsequent lines of space-separated integers each describe the respective tolls or traveling from city to city ; in other words, the integer of the line denotes the toll for traveling from city to city .

Note: As there are no roads connecting a city to itself, the integer of line will always be .

Constraints


Output Format

Print the minimum cost as a rational number (tolls paid over roads traveled). The greatest common divisor of and should be .

Sample Input

2
0 1
2 0

Sample Output

3/2

Explanation

The toll from city to city is . The toll from to is . Your travel cost . Your number of roads traveled is . Thus, we print 3/2 as our answer.

Limbajul de programare folosit: cpp14

Cod:

#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() {
    int input, s, roads[MAXN][MAXN], cities[MAXN][MAXN];
    pair<int, int> directions, max_roads;

    while (cin >> input) {
        for (int i = 0; i < input; i++) {
            for (int j = 0; j < input; j++) {
                cin >> roads[i][j];

                if (i == j)
                    roads[i][j] = INFINITY;
            }
        }

        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++) {
            roads[s][i] = 0;
            roads[i][s] = INFINITY;
        }

        roads[s][s] = INFINITY;
        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;

            max_roads = make_pair(-INFINITY, 1);

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

            if (get_difference(max_roads, directions) < 0)
                directions = max_roads;
        }

        get_min_cost(directions);
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464612525

Link challenge: https://www.hackerrank.com/challenges/hacker-country/problem

Hacker Country