Statistics

Problem Statement for "Spanning"

Problem Statement

Given a connected graph with nodes nodes, where each edge is undirected and has both a length and a cost, your task is to pick a subset of the edges such that the graph is still connected, the minimum distance between each pair of nodes is less than or equal to threshold, and the total cost is minimized. You should return this minimum cost. The graph will be given as a String[], g, each element of which represents an edge in the form "u v length cost", where u and v are the zero-based indices of the two nodes connected by this edge. For example, consider the following input:
nodes = 3
threshold = 5
g = {"0 1 4 1","0 2 3 2","1 2 1 4"}
If we select the first and second edges, then the distance between nodes 1 and 2 ends up being 7, greater than our threshold. However, if we pick the first and third edges, the distance between all pairs of nodes is 5 or less, and the cost is minimized (picking the second and third edges would cost more). Thus, we return the cost of these two edges, 5.

Definition

Class:
Spanning
Method:
cost
Parameters:
String[], int, int
Returns:
int
Method signature:
int cost(String[] g, int nodes, int threshold)
(be sure your method is public)

Constraints

  • g will contain between 1 and 18 elements, inclusive.
  • nodes will be between 2 and 10, inclusive.
  • threshold will be between 1 and 1000, inclusive.
  • Each element of g will be formatted as "u v length cost", where u, v, length and cost are all integers with no extra leading zeros.
  • Each u and v will be between 0 and nodes-1, inclusive.
  • Each length and cost will be between 1 and 100, inclusive.
  • No two elements of g will refer to edges between the same pair of nodes.
  • In each element of g, u will not equal v.
  • If you use all of the edges, the graph will be connected, and the minimum distance between each pair of nodes will be less than or equal to threshold.

Examples

  1. {"0 1 4 1","0 2 3 2","1 2 1 4"}

    3

    5

    Returns: 5

  2. {"2 3 7 1", "3 1 9 1", "1 0 8 1", "3 0 1 5", "1 2 5 7", "0 2 8 4"}

    4

    1000

    Returns: 3

    With the threshold this high, we just need to find the cheapest way to connect all the nodes. It turns out that the first, second and third edges do this cheapest.

  3. {"2 3 7 1", "3 1 9 1", "1 0 8 1", "3 0 1 5", "1 2 5 7", "0 2 8 4"}

    4

    10

    Returns: 14

    With the same graph, but a lower threshold, the best edges to use are the first, third, fourth, and fifth.

  4. {"6 8 19 19","1 3 98 75","6 7 60 91","4 6 89 53","2 7 84 100","9 5 31 65","8 7 51 80","1 4 78 94","9 3 68 43","7 0 20 77","4 7 89 20","4 2 82 21","8 0 30 36","8 3 44 100","1 8 41 56","8 2 27 66","7 5 50 3","9 7 45 71"}

    10

    190

    Returns: 442

  5. {"8 7 9 18","2 3 29 44","7 0 37 19","1 7 56 48","5 8 99 71","9 6 7 15","8 3 4 54","4 5 88 48","7 3 38 29","5 6 80 96","9 1 44 89","5 2 14 7","0 8 75 62","2 0 43 27","3 4 84 36","5 7 20 67","6 7 23 18","0 9 38 36"}

    10

    950

    Returns: 217

  6. {"8 1 42 53","4 0 8 22","6 2 94 40","9 4 37 15","6 1 30 28","2 3 68 100","2 7 29 33","6 9 27 84","4 1 90 6","5 3 82 24","3 7 48 79","8 2 54 53","1 2 2 17","9 8 74 95","4 2 86 42","0 5 21 58","3 1 99 8","0 7 16 15"}

    10

    452

    Returns: 188

  7. {"4 1 7 67","3 0 1 65","4 2 47 6","9 8 26 72","0 2 15 70","8 5 69 33","4 5 58 79","4 0 45 45","6 5 3 13","3 9 3 58","3 5 42 1","4 6 13 89","7 3 53 7","1 3 46 69","2 3 72 57","8 7 77 87","6 8 5 100","7 5 62 2"}

    10

    849

    Returns: 282

  8. {"1 0 83 93","5 6 92 100","7 0 83 86","9 5 39 81","3 9 3 38","7 8 65 40","9 4 96 14","3 8 94 50","4 1 97 43","6 8 88 82","2 1 85 3","1 6 96 37","7 2 14 47","7 3 17 54","5 0 11 6","6 9 99 90","5 2 77 21","9 8 75 98"}

    10

    603

    Returns: 249

  9. {"4 8 11 9","3 9 31 45","0 5 19 56","8 1 65 41","2 8 76 14","9 1 65 8","8 7 86 13","5 4 33 56","5 8 18 70","4 2 31 96","4 3 76 84","3 6 35 9","1 7 72 43","5 9 5 61","5 1 17 80","0 8 40 64","7 3 93 32","4 7 26 94"}

    10

    200

    Returns: 285

  10. {"1 6 3 18","4 8 57 88","0 4 11 98","6 9 91 65","3 8 3 91","1 5 54 80","9 1 97 8","5 2 4 19","6 4 22 17","1 7 62 57","4 7 97 17","8 5 84 74","0 7 22 44","2 4 74 59","8 7 43 34","9 3 57 52","1 2 22 36","5 6 45 10"}

    10

    911

    Returns: 219

  11. {"6 3 57 35", "6 1 84 16", "3 4 91 10", "0 7 66 7", "5 2 16 51", "5 3 68 69", "6 0 26 55", "4 1 11 27"}

    8

    236

    Returns: 260

  12. {"0 8 49 22","7 3 82 44","4 0 99 21","9 6 12 27","6 0 48 21","1 5 66 26","7 5 38 8","9 4 45 5","3 0 6 44","4 3 65 96","1 4 22 73","2 5 100 72","1 3 88 1","5 8 54 2","7 6 47 15","5 0 86 56","7 4 59 55","5 9 17 60"}

    10

    834

    Returns: 171

  13. {"0 1 5 5"}

    2

    100

    Returns: 5

  14. {"1 3 98 7", "2 3 84 10", "1 4 78 9", "4 0 82 2", "3 0 95 4"}

    5

    1000

    Returns: 23

  15. { "0 1 10 20", "0 2 10 20", "1 2 10 20", "1 3 10 20", "2 3 10 20", "2 4 10 20", "3 4 10 20", "3 5 10 20", "4 5 10 20", "4 6 10 20", "5 6 10 20", "5 7 10 20", "6 7 10 20", "6 8 10 20", "7 8 10 20", "7 9 10 20", "8 9 10 20", "8 0 10 20"}

    10

    39

    Returns: 240

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: