Statistics

Problem Statement for "CostMatrix"

Problem Statement

An airline company has flights to all major cities in some country. From any major city it is possible to reach any other major city either by a direct flight, or by two or more flights. The company has provided a matrix containing the cheapest cost when taking a trip between any pair of major cities. When several flights are needed for a trip, the cost for that trip is the sum of the costs of the direct flights. The cost for a direct flight is a positive integer.

Given this matrix, you want to find the least possible total cost of all direct flights. You can assume that if a flight exists from A to B, another flight with the same cost exists from B to A (and you should only count one of these direct flights), and that no other flights between the same pair of cities exist with a different cost.

Create a class CostMatrix containing the method leastTotalCost which takes as input a String[] matrix, describing the cost matrix as a symmetric table. Each row i (0-indexed) will contain a single space separated list of integers, where the jth integer (0-indexed) in row i is the cheapest cost to take a trip between cities i and j. The diagonal entries will all be 0. The method should return an int, the least possible total cost for all direct flights. If the cost matrix is inconsistent, return -1.

Definition

Class:
CostMatrix
Method:
leastTotalCost
Parameters:
String[]
Returns:
int
Method signature:
int leastTotalCost(String[] matrix)
(be sure your method is public)

Constraints

  • matrix will contain between 2 and 20 elements, inclusive.
  • Each element in matrix will be a single-space separated list of non-negative integers without leading or trailing spaces.
  • The number of integers in each element in matrix will be the same as the number of elements in matrix.
  • The ith integer in element j, where i != j, will be between 1 and 2500, inclusive, without leading zeros.
  • The ith integer in element i will be 0.
  • The ith integer in element j will be equal to the jth integer in element i.

Examples

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

    Returns: 6

    The only possible network of flight routes consists of three direct flights, each with cost 2, connecting every pair of cities, for a total cost of 6.

  2. {"0 6 15 2 6", "6 0 9 8 12", "15 9 0 16 18", "2 8 16 0 4", "6 12 18 4 0"}

    Returns: 55

    The least possible cost consists of the direct flights: City 0 - city 1 (cost 6) City 1 - city 2 (cost 9) City 0 - city 3 (cost 2) City 2 - city 3 (cost 16) City 3 - city 4 (cost 4) City 2 - city 4 (cost 18)

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

    Returns: -1

  4. {"0 1 6 17 26 13 7 16", "1 0 5 16 25 12 7 15", "6 5 0 21 21 8 12 11", "17 16 21 0 41 28 23 31", "26 25 21 41 0 13 32 10", "13 12 8 28 13 0 19 3", "7 7 12 23 32 19 0 22", "16 15 11 31 10 3 22 0"}

    Returns: 69

  5. {"0 934 548 750","934 0 1482 184","548 1482 0 1298","750 184 1298 0"}

    Returns: 1482

  6. {"0 585 701 59","585 0 313 526","701 313 0 760","59 526 760 0"}

    Returns: 1599

  7. {"0 938 285 340","938 0 1010 955","285 1010 0 55","340 955 55 0"}

    Returns: 2233

  8. {"0 11 10 14 13 5 8 6 8 5 9 4 10 9 13 7","11 0 16 17 13 8 11 9 11 8 2 7 13 9 16 10","10 16 0 17 18 10 13 7 13 8 14 9 15 19 18 12","14 17 17 0 17 11 12 10 14 9 15 10 6 22 15 9","13 13 18 17 0 10 13 11 13 10 14 9 15 21 18 12","5 8 10 11 10 0 5 3 5 2 6 1 7 13 10 4","8 11 13 12 13 5 0 6 8 5 9 4 10 16 13 7","6 9 7 10 11 3 6 0 6 1 7 2 8 14 11 5","8 11 13 14 13 5 8 6 0 5 9 4 10 16 13 7","5 8 8 9 10 2 5 1 5 0 6 1 7 13 10 4","9 2 14 15 14 6 9 7 9 6 0 5 11 7 14 8","4 7 9 10 9 1 4 2 4 1 5 0 6 12 9 3","10 13 15 6 15 7 10 8 10 7 11 6 0 18 9 3","9 9 19 22 21 13 16 14 16 13 7 12 18 0 21 15","13 16 18 15 18 10 13 11 13 10 14 9 9 21 0 6","7 10 12 9 12 4 7 5 7 4 8 3 3 15 6 0"}

    Returns: 133

  9. {"0 107 73 50 66 10 81 46 83 71 65 71 87","107 0 50 82 41 117 50 86 49 103 42 81 43","73 50 0 113 9 83 100 117 96 92 8 131 93","50 82 113 0 116 60 46 4 33 21 115 73 39","66 41 9 116 0 76 91 112 87 101 1 122 84","10 117 83 60 76 0 71 56 84 77 75 81 78","81 50 100 46 91 71 0 50 13 67 92 52 7","46 86 117 4 112 56 50 0 37 25 111 77 43","83 49 96 33 87 84 13 37 0 54 88 40 6","71 103 92 21 101 77 67 25 54 0 100 94 60","65 42 8 115 1 75 92 111 88 100 0 123 85","71 81 131 73 122 81 52 77 40 94 123 0 46","87 43 93 39 84 78 7 43 6 60 85 46 0"}

    Returns: 943

  10. {"0 17 11 5 9 6 9 8 11 4 5 17 6 10 4 7","17 0 13 12 10 11 9 11 7 17 14 18 13 10 13 15","11 13 0 11 13 10 11 9 13 15 6 6 11 12 12 8","5 12 11 0 6 1 4 6 6 5 6 15 1 5 1 8","9 10 13 6 0 7 2 4 4 11 7 13 7 3 7 8","6 11 10 1 7 0 5 7 7 6 6 16 2 6 2 8","9 9 11 4 2 5 0 2 2 9 5 11 5 1 5 6","8 11 9 6 4 7 2 0 4 11 3 13 7 3 7 5","11 7 13 6 4 7 2 4 0 11 7 13 7 3 7 8","4 17 15 5 11 6 9 11 11 0 9 20 6 10 6 11","5 14 6 6 7 6 5 3 7 9 0 12 5 6 6 2","17 18 6 15 13 16 11 13 13 20 12 0 16 12 16 14","6 13 11 1 7 2 5 7 7 6 5 16 0 6 2 7","10 10 12 5 3 6 1 3 3 10 6 12 6 0 6 5","4 13 12 1 7 2 5 7 7 6 6 16 2 6 0 8","7 15 8 8 8 8 6 5 8 11 2 14 7 5 8 0"}

    Returns: 160

  11. {"0 10 4 10 10 5 14 12 12 7 21 19 13 7 15 11 23","10 0 14 11 6 5 21 8 9 14 18 16 17 3 11 8 19","4 14 0 6 14 9 18 9 16 3 24 18 17 11 11 15 27","10 11 6 0 11 10 22 3 10 3 19 17 18 8 11 9 21","10 6 14 11 0 5 15 8 3 12 12 10 12 3 5 2 13","5 5 9 10 5 0 19 7 8 12 17 15 12 2 10 7 18","14 21 18 22 15 19 0 22 14 21 12 5 8 18 20 13 15","12 8 9 3 8 7 22 0 11 6 20 18 19 5 13 10 21","12 9 16 10 3 8 14 11 0 13 11 9 11 6 8 1 14","7 14 3 3 12 12 21 6 13 0 21 20 20 11 8 12 24","21 18 24 19 12 17 12 20 11 21 0 17 19 15 17 10 3","19 16 18 17 10 15 5 18 9 20 17 0 13 13 15 8 20","13 17 17 18 12 12 8 19 11 20 19 13 0 14 17 10 16","7 3 11 8 3 2 18 5 6 11 15 13 14 0 8 5 16","15 11 11 11 5 10 20 13 8 8 17 15 17 8 0 7 18","11 8 15 9 2 7 13 10 1 12 10 8 10 5 7 0 13","23 19 27 21 13 18 15 21 14 24 3 20 16 16 18 13 0"}

    Returns: 303

  12. {"0 89 45 40 41 95 87 76 85 65 59 8","89 0 63 91 66 89 51 40 79 63 35 81","45 63 0 85 4 74 78 67 64 44 35 53","40 91 85 0 81 77 104 93 67 87 99 32","41 66 4 81 0 70 74 63 60 40 31 49","95 89 74 77 70 0 55 53 10 30 54 103","87 51 78 104 74 55 0 11 45 34 57 95","76 40 67 93 63 53 11 0 43 23 46 84","85 79 64 67 60 10 45 43 0 20 44 93","65 63 44 87 40 30 34 23 20 0 64 73","59 35 35 99 31 54 57 46 44 64 0 67","8 81 53 32 49 103 95 84 93 73 67 0"}

    Returns: 1025

  13. {"0 235 56 221 104 180 236 153 310 166 143","235 0 179 248 131 55 263 180 75 193 170","56 179 0 165 48 124 180 97 254 110 87","221 248 165 0 117 193 249 68 323 179 156","104 131 48 117 0 76 132 49 206 62 39","180 55 124 193 76 0 208 125 130 138 115","236 263 180 249 132 208 0 181 338 116 93","153 180 97 68 49 125 181 0 255 111 88","310 75 254 323 206 130 338 255 0 268 245","166 193 110 179 62 138 116 111 268 0 23","143 170 87 156 39 115 93 88 245 23 0"}

    Returns: 582

  14. {"0 28 26 27 19 49 19 54 42 53 30 12 24","28 0 30 1 47 36 37 28 14 44 34 16 42","26 30 0 29 45 65 35 56 44 57 32 14 40","27 1 29 0 46 37 36 27 15 43 33 15 41","19 47 45 46 0 67 38 53 61 69 28 31 43","49 36 65 37 67 0 30 64 50 80 64 51 35","19 37 35 36 38 30 0 42 34 58 34 21 5","54 28 56 27 53 64 42 0 42 16 30 42 37","42 14 44 15 61 50 34 42 0 55 43 30 39","53 44 57 43 69 80 58 16 55 0 46 58 53","30 34 32 33 28 64 34 30 43 46 0 18 29","12 16 14 15 31 51 21 42 30 58 18 0 26","24 42 40 41 43 35 5 37 39 53 29 26 0"}

    Returns: 733

  15. {"0 47 60 49 67 56 91 35 88 84 51 67 60 39","47 0 37 26 44 33 68 12 65 59 28 44 107 16","60 37 0 39 57 14 81 25 78 42 9 25 120 29","49 26 39 0 34 35 42 14 39 63 30 46 109 18","67 44 57 34 0 53 76 32 73 81 48 64 127 28","56 33 14 35 53 0 72 21 74 28 5 21 116 25","91 68 81 42 76 72 0 56 81 44 72 88 151 60","35 12 25 14 32 21 56 0 53 49 16 32 95 4","88 65 78 39 73 74 81 53 0 102 69 85 148 57","84 59 42 63 81 28 44 49 102 0 33 49 144 53","51 28 9 30 48 5 72 16 69 33 0 16 111 20","67 44 25 46 64 21 88 32 85 49 16 0 127 36","60 107 120 109 127 116 151 95 148 144 111 127 0 99","39 16 29 18 28 25 60 4 57 53 20 36 99 0"}

    Returns: 445

  16. {"0 65 67 118 44 103 104 66 69 73 52 55 96 97","65 0 14 53 27 70 51 67 16 20 19 10 39 60","67 14 0 67 41 84 37 53 2 6 33 24 29 46","118 53 67 0 80 123 102 104 69 73 72 63 92 39","44 27 41 80 0 59 60 94 43 47 8 17 66 73","103 70 84 123 59 0 119 78 86 90 51 60 109 116","104 51 37 102 60 119 0 68 39 43 68 61 12 63","66 67 53 104 94 78 68 0 51 47 86 77 56 65","69 16 2 69 43 86 39 51 0 4 35 26 27 44","73 20 6 73 47 90 43 47 4 0 39 30 31 40","52 19 33 72 8 51 68 86 35 39 0 9 58 65","55 10 24 63 17 60 61 77 26 30 9 0 49 56","96 39 29 92 66 109 12 56 27 31 58 49 0 71","97 60 46 39 73 116 63 65 44 40 65 56 71 0"}

    Returns: 1099

  17. {"0 43 12 54 5 121 43 35 63 10 58","43 0 55 32 48 155 86 61 106 53 92","12 55 0 42 17 109 35 23 61 2 46","54 32 42 0 59 123 77 29 103 44 60","5 48 17 59 0 126 48 40 58 15 63","121 155 109 123 126 0 102 94 77 111 63","43 86 35 77 48 102 0 58 26 33 39","35 61 23 29 40 94 58 0 84 25 31","63 106 61 103 58 77 26 84 0 59 65","10 53 2 44 15 111 33 25 59 0 48","58 92 46 60 63 63 39 31 65 48 0"}

    Returns: 559

  18. {"0 476 527 1043 54 880 389 567 249","476 0 225 741 422 578 87 265 617","527 225 0 792 473 629 138 316 668","1043 741 792 0 989 163 654 639 1184","54 422 473 989 0 826 335 513 195","880 578 629 163 826 0 491 476 1021","389 87 138 654 335 491 0 178 530","567 265 316 639 513 476 178 0 708","249 617 668 1184 195 1021 530 708 0"}

    Returns: 2117

  19. {"0 133 105 145 132 93 190 160 229 186 174 186 57","133 0 208 12 79 40 192 153 134 110 41 53 190","105 208 0 196 230 191 85 55 124 98 225 155 48","145 12 196 0 91 52 180 141 122 98 29 41 202","132 79 230 91 0 39 214 175 213 132 120 132 189","93 40 191 52 39 0 175 136 174 93 81 93 150","190 192 85 180 214 175 0 125 194 82 209 139 133","160 153 55 141 175 136 125 0 69 43 170 100 103","229 134 124 122 213 174 194 69 0 112 151 81 172","186 110 98 98 132 93 82 43 112 0 127 57 146","174 41 225 29 120 81 209 170 151 127 0 70 231","186 53 155 41 132 93 139 100 81 57 70 0 203","57 190 48 202 189 150 133 103 172 146 231 203 0"}

    Returns: 924

  20. {"0 16 16 15 14 4 10 18 14 15 11 2 12 3 20 14","16 0 9 12 10 15 6 6 11 12 19 15 4 14 16 11","16 9 0 9 14 16 6 10 10 11 16 14 5 15 15 7","15 12 9 0 6 15 10 10 1 2 7 16 8 15 16 15","14 10 14 6 0 14 16 4 7 7 13 12 14 13 11 11","4 15 16 15 14 0 11 18 14 15 9 2 13 1 18 16","10 6 6 10 16 11 0 12 9 10 17 9 2 10 17 9","18 6 10 10 4 18 12 0 9 8 17 16 10 17 10 15","14 11 10 1 7 14 9 9 0 1 8 15 7 15 17 14","15 12 11 2 7 15 10 8 1 0 9 16 8 16 18 15","11 19 16 7 13 9 17 17 8 9 0 9 15 8 9 17","2 15 14 16 12 2 9 16 15 16 9 0 11 1 18 15","12 4 5 8 14 13 2 10 7 8 15 11 0 12 15 7","3 14 15 15 13 1 10 17 15 16 8 1 12 0 17 15","20 16 15 16 11 18 17 10 17 18 9 18 15 17 0 8","14 11 7 15 11 16 9 15 14 15 17 15 7 15 8 0"}

    Returns: 304

  21. {"0 44 269 390 258 253 299 342","44 0 225 367 275 209 255 386","269 225 0 283 50 227 30 247","390 367 283 0 333 158 313 530","258 275 50 333 0 277 80 297","253 209 227 158 277 0 257 474","299 255 30 313 80 257 0 277","342 386 247 530 297 474 277 0"}

    Returns: 2463

  22. {"0 14 3 13 9 10 10 12 14 10 12 12 6 7 4","14 0 11 5 13 12 19 11 8 4 10 15 8 9 12","3 11 0 10 8 7 13 9 11 7 11 9 3 4 1","13 5 10 0 15 9 21 13 13 9 15 15 7 8 11","9 13 8 15 0 14 6 7 5 9 3 11 10 11 9","10 12 7 9 14 0 20 8 12 8 12 12 4 3 6","10 19 13 21 6 20 0 13 11 15 9 17 16 17 14","12 11 9 13 7 8 13 0 6 10 4 4 6 5 8","14 8 11 13 5 12 11 6 0 4 2 10 8 9 12","10 4 7 9 9 8 15 10 4 0 6 12 4 5 8","12 10 11 15 3 12 9 4 2 6 0 8 10 9 12","12 15 9 15 11 12 17 4 10 12 8 0 8 9 10","6 8 3 7 10 4 16 6 8 4 10 8 0 1 4","7 9 4 8 11 3 17 5 9 5 9 9 1 0 3","4 12 1 11 9 6 14 8 12 8 12 10 4 3 0"}

    Returns: 151

  23. {"0 202 125 244 193 217 271 147 159","202 0 178 45 77 72 69 156 43","125 178 0 220 169 193 247 22 135","244 45 220 0 51 27 114 198 85","193 77 169 51 0 24 146 147 34","217 72 193 27 24 0 141 171 58","271 69 247 114 146 141 0 225 112","147 156 22 198 147 171 225 0 113","159 43 135 85 34 58 112 113 0"}

    Returns: 661

  24. {"0 62 57 54 56 79 60 24 73 39 92 37 41 41","62 0 31 34 70 21 47 38 15 23 55 68 55 71","57 31 0 3 45 22 48 33 16 48 86 44 50 54","54 34 3 0 48 25 51 30 19 45 89 41 47 51","56 70 45 48 0 65 39 32 61 47 84 89 15 83","79 21 22 25 65 0 26 55 6 44 76 66 72 62","60 47 48 51 39 26 0 71 32 70 54 78 54 44","24 38 33 30 32 55 71 0 49 15 82 60 17 65","73 15 16 19 61 6 32 49 0 38 70 60 66 56","39 23 48 45 47 44 70 15 38 0 78 45 32 58","92 55 86 89 84 76 54 82 70 78 0 55 69 94","37 68 44 41 89 66 78 60 60 45 55 0 77 39","41 55 50 47 15 72 54 17 66 32 69 77 0 82","41 71 54 51 83 62 44 65 56 58 94 39 82 0"}

    Returns: 1139

  25. {"0 235 895 1615 697 1120","235 0 660 1380 462 885","895 660 0 961 198 621","1615 1380 961 0 918 543","697 462 198 918 0 423","1120 885 621 543 423 0"}

    Returns: 3740

  26. {"0 84 88 304 350 109 334 219 270 13","84 0 172 329 354 36 250 135 186 71","88 172 0 370 330 197 291 176 227 101","304 329 370 0 46 365 79 194 143 291","350 354 330 46 0 390 125 219 168 337","109 36 197 365 390 0 286 171 222 96","334 250 291 79 125 286 0 115 64 321","219 135 176 194 219 171 115 0 51 206","270 186 227 143 168 222 64 51 0 257","13 71 101 291 337 96 321 206 257 0"}

    Returns: 1644

  27. {"0 886 673 464 237 801 432 470","886 0 686 422 963 759 768 428","673 686 0 264 436 601 241 258","464 422 264 0 541 337 346 6","237 963 436 541 0 878 195 547","801 759 601 337 878 0 683 343","432 768 241 346 195 683 0 352","470 428 258 6 547 343 352 0"}

    Returns: 2506

  28. {"0 300 1157 610 1730 390 1280 746","300 0 857 642 1430 422 980 446","1157 857 0 1499 573 1279 123 411","610 642 1499 0 2072 220 1622 1088","1730 1430 573 2072 0 1852 450 984","390 422 1279 220 1852 0 1402 868","1280 980 123 1622 450 1402 0 534","746 446 411 1088 984 868 534 0"}

    Returns: 2762

  29. {"0 9 75 49 45 60 14 61 15 3 14 43","9 0 80 58 47 51 23 70 6 12 14 34","75 80 0 79 66 69 77 67 81 78 89 53","49 58 79 0 53 45 63 12 64 52 55 40","45 47 66 53 0 30 53 62 41 42 59 13","60 51 69 45 30 0 47 57 45 58 56 17","14 23 77 63 53 47 0 75 29 11 24 57","61 70 67 12 62 57 75 0 76 64 67 52","15 6 81 64 41 45 29 76 0 18 20 28","3 12 78 52 42 58 11 64 18 0 17 46","14 14 89 55 59 56 24 67 20 17 0 48","43 34 53 40 13 17 57 52 28 46 48 0"}

    Returns: 968

  30. {"0 105 103 99 134 81 102 72 120 141 114 152 80","105 0 10 6 29 99 3 63 65 36 15 65 25","103 10 0 4 39 97 7 73 63 46 19 55 23","99 6 4 0 35 93 3 69 59 42 15 59 19","134 29 39 35 0 128 32 92 51 7 44 41 54","81 99 97 93 128 0 96 153 152 135 108 152 112","102 3 7 3 32 96 0 66 62 39 12 62 22","72 63 73 69 92 153 66 0 48 92 78 126 88","120 65 63 59 51 152 62 48 0 44 74 78 40","141 36 46 42 7 135 39 92 44 0 48 34 61","114 15 19 15 44 108 12 78 74 48 0 56 34","152 65 55 59 41 152 62 126 78 34 56 0 72","80 25 23 19 54 112 22 88 40 61 34 72 0"}

    Returns: 863

  31. {"0 154 387 151 381 371 456 372","154 0 239 3 350 223 315 224","387 239 0 236 167 325 76 15","151 3 236 0 353 220 312 221","381 350 167 353 0 492 243 152","371 223 325 220 492 0 401 340","456 315 76 312 243 401 0 91","372 224 15 221 152 340 91 0"}

    Returns: 2350

  32. {"0 1093 990 625","1093 0 103 1064","990 103 0 961","625 1064 961 0"}

    Returns: 2679

  33. {"0 5 9 1 15 3 4 6 9 5 2 12 12 11 3","5 0 10 4 16 4 7 8 12 6 3 15 15 12 6","9 10 0 8 19 6 11 10 16 8 7 11 19 16 10","1 4 8 0 14 2 3 6 8 4 1 11 11 10 2","15 16 19 14 0 13 16 9 21 11 13 20 6 4 15","3 4 6 2 13 0 5 4 10 2 1 13 13 10 4","4 7 11 3 16 5 0 9 5 7 4 8 10 13 1","6 8 10 6 9 4 9 0 14 2 5 11 15 13 8","9 12 16 8 21 10 5 14 0 12 9 13 15 17 6","5 6 8 4 11 2 7 2 12 0 3 13 15 12 6","2 3 7 1 13 1 4 5 9 3 0 12 12 9 3","12 15 11 11 20 13 8 11 13 13 12 0 18 21 9","12 15 19 11 6 13 10 15 15 15 12 18 0 10 9","11 12 16 10 4 10 13 13 17 12 9 21 10 0 12","3 6 10 2 15 4 1 8 6 6 3 9 9 12 0"}

    Returns: 114

  34. {"0 545 447 138 98","545 0 757 683 447","447 757 0 585 349","138 683 585 0 236","98 447 349 236 0"}

    Returns: 1789

  35. {"0 98 60 79 85 18 77 74 69 76 47 52 75 63","98 0 59 60 71 107 65 73 44 85 56 51 67 79","60 59 0 35 51 64 32 30 35 42 13 8 30 37","79 60 35 0 43 83 5 39 16 61 32 27 7 19","85 71 51 43 0 95 38 65 59 67 38 43 36 24","18 107 64 83 95 0 88 78 83 90 61 56 90 81","77 65 32 5 38 88 0 34 21 66 37 32 2 14","74 73 30 39 65 78 34 0 49 56 27 22 36 48","69 44 35 16 59 83 21 49 0 51 22 27 23 35","76 85 42 61 67 90 66 56 51 0 29 34 65 53","47 56 13 32 38 61 37 27 22 29 0 5 36 24","52 51 8 27 43 56 32 22 27 34 5 0 34 29","75 67 30 7 36 90 2 36 23 65 36 34 0 12","63 79 37 19 24 81 14 48 35 53 24 29 12 0"}

    Returns: 841

  36. {"0 744 32 1315 974 524","744 0 712 571 1718 1268","32 712 0 1283 1006 556","1315 571 1283 0 2289 1839","974 1718 1006 2289 0 450","524 1268 556 1839 450 0"}

    Returns: 2289

  37. {"0 362 517 968 628","362 0 155 606 266","517 155 0 620 145","968 606 620 0 765","628 266 145 765 0"}

    Returns: 2154

  38. {"0 24 18 28 38 52 29 21 30 17 43 51 74 68","24 0 8 15 24 40 11 3 17 7 30 38 56 55","18 8 0 23 20 36 13 5 25 1 38 46 58 63","28 15 23 0 13 46 26 18 2 22 15 23 65 40","38 24 20 13 0 55 13 21 11 21 28 36 58 53","52 40 36 46 55 0 45 37 44 35 43 69 90 32","29 11 13 26 13 45 0 8 24 12 41 49 45 66","21 3 5 18 21 37 8 0 20 4 33 41 53 58","30 17 25 2 11 44 24 20 0 24 17 25 63 42","17 7 1 22 21 35 12 4 24 0 37 45 57 62","43 30 38 15 28 43 41 33 17 37 0 38 80 55","51 38 46 23 36 69 49 41 25 45 38 0 88 63","74 56 58 65 58 90 45 53 63 57 80 88 0 105","68 55 63 40 53 32 66 58 42 62 55 63 105 0"}

    Returns: 499

  39. {"0 3 38 35 2 9 18 13 46 19 18 1 7 20","3 0 35 38 5 12 21 10 49 22 21 4 10 17","38 35 0 57 40 31 49 25 78 51 40 39 33 18","35 38 57 0 37 26 53 46 81 46 53 36 28 39","2 5 40 37 0 11 20 15 44 17 16 1 9 22","9 12 31 26 11 0 27 20 55 20 27 10 2 13","18 21 49 53 20 27 0 31 64 37 34 19 25 38","13 10 25 46 15 20 31 0 59 32 29 14 20 7","46 49 78 81 44 55 64 59 0 61 60 45 53 60","19 22 51 46 17 20 37 32 61 0 33 18 22 33","18 21 40 53 16 27 34 29 60 33 0 17 25 22","1 4 39 36 1 10 19 14 45 18 17 0 8 21","7 10 33 28 9 2 25 20 53 22 25 8 0 15","20 17 18 39 22 13 38 7 60 33 22 21 15 0"}

    Returns: 368

  40. {"0 658 65 637","658 0 723 1295","65 723 0 662","637 1295 662 0"}

    Returns: 2022

  41. {"0 6 8 9 4 4 7 6 6 2 1 9 10 9 3 5 5 10 2 11","6 0 11 15 7 10 10 9 9 8 7 12 14 12 9 10 8 13 4 15","8 11 0 13 10 10 13 10 12 10 9 8 6 5 11 9 11 4 7 5","9 15 13 0 8 6 11 6 8 8 8 5 7 9 10 5 7 10 11 8","4 7 10 8 0 6 3 4 2 6 3 5 7 9 5 5 1 10 3 8","4 10 10 6 6 0 9 2 4 2 5 7 8 5 7 1 5 6 6 9","7 10 13 11 3 9 0 7 5 9 6 8 10 12 8 8 4 13 6 11","6 9 10 6 4 2 7 0 2 4 7 9 10 5 9 1 3 6 5 9","6 9 12 8 2 4 5 2 0 6 5 7 9 7 7 3 1 8 5 10","2 8 10 8 6 2 9 4 6 0 3 9 10 7 5 3 7 8 4 11","1 7 9 8 3 5 6 7 5 3 0 8 9 10 2 6 4 11 3 10","9 12 8 5 5 7 8 9 7 9 8 0 2 10 9 8 6 9 8 3","10 14 6 7 7 8 10 10 9 10 9 2 0 8 7 9 8 7 10 1","9 12 5 9 9 5 12 5 7 7 10 10 8 0 12 4 8 1 10 9","3 9 11 10 5 7 8 9 7 5 2 9 7 12 0 8 6 13 5 8","5 10 9 5 5 1 8 1 3 3 6 8 9 4 8 0 4 5 6 10","5 8 11 7 1 5 4 3 1 7 4 6 8 8 6 4 0 9 4 9","10 13 4 10 10 6 13 6 8 8 11 9 7 1 13 5 9 0 11 8","2 4 7 11 3 6 6 5 5 4 3 8 10 10 5 6 4 11 0 11","11 15 5 8 8 9 11 9 10 11 10 3 1 9 8 10 9 8 11 0"}

    Returns: 145

  42. {"0 405 498 34","405 0 835 371","498 835 0 464","34 371 464 0"}

    Returns: 869

  43. {"0 215 295 161 200 63 261 170 305","215 0 181 235 247 278 126 217 90","295 181 0 134 176 253 55 146 271","161 235 134 0 273 224 152 243 325","200 247 176 273 0 137 121 30 337","63 278 253 224 137 0 198 107 368","261 126 55 152 121 198 0 91 216","170 217 146 243 30 107 91 0 307","305 90 271 325 337 368 216 307 0"}

    Returns: 1459

  44. {"0 16 26 12 27 24 34 14 21 10 24 33 20 24 24 7","16 0 10 15 11 8 18 2 5 6 12 17 16 8 15 9","26 10 0 25 21 18 8 12 15 16 10 7 26 2 22 19","12 15 25 0 19 23 33 17 14 18 27 27 8 23 30 19","27 11 21 19 0 19 29 13 6 17 23 19 21 19 26 20","24 8 18 23 19 0 26 10 13 14 14 20 24 16 15 17","34 18 8 33 29 26 0 20 23 24 18 15 34 10 14 27","14 2 12 17 13 10 20 0 7 4 10 19 14 10 17 7","21 5 15 14 6 13 23 7 0 11 17 13 21 13 20 14","10 6 16 18 17 14 24 4 11 0 14 23 10 14 21 11","24 12 10 27 23 14 18 10 17 14 0 17 24 12 17 17","33 17 7 27 19 20 15 19 13 23 17 0 33 9 28 26","20 16 26 8 21 24 34 14 21 10 24 33 0 24 31 21","24 8 2 23 19 16 10 10 13 14 12 9 24 0 23 17","24 15 22 30 26 15 14 17 20 21 17 28 31 23 0 24","7 9 19 19 20 17 27 7 14 11 17 26 21 17 24 0"}

    Returns: 353

  45. {"0 353 145 317 468 417 240 265 355 748","353 0 385 339 275 439 416 265 231 770","145 385 0 172 323 272 95 120 210 603","317 339 172 0 221 100 77 198 108 431","468 275 323 221 0 321 298 203 113 652","417 439 272 100 321 0 177 298 208 531","240 416 95 77 298 177 0 215 185 508","265 265 120 198 203 298 215 0 90 629","355 231 210 108 113 208 185 90 0 539","748 770 603 431 652 531 508 629 539 0"}

    Returns: 2403

  46. {"0 54 30 40 29 38 17 53 32 37 22 26","54 0 40 27 31 49 38 38 34 24 32 28","30 40 0 18 34 25 22 39 18 21 8 12","40 27 18 0 44 35 32 30 28 3 18 22","29 31 34 44 0 33 12 25 28 41 26 22","38 49 25 35 33 0 21 48 27 32 17 21","17 38 22 32 12 21 0 37 16 29 14 10","53 38 39 30 25 48 37 0 33 33 31 27","32 34 18 28 28 27 16 33 0 25 10 6","37 24 21 3 41 32 29 33 25 0 15 19","22 32 8 18 26 17 14 31 10 15 0 4","26 28 12 22 22 21 10 27 6 19 4 0"}

    Returns: 356

  47. {"0 273 414 419 397 125 374 26 213","273 0 305 146 401 346 243 247 82","414 305 0 340 557 289 229 388 223","419 146 340 0 255 492 389 393 228","397 401 557 255 0 272 328 371 483","125 346 289 492 272 0 456 99 338","374 243 229 389 328 456 0 357 161","26 247 388 393 371 99 357 0 239","213 82 223 228 483 338 161 239 0"}

    Returns: 3267

  48. {"0 279 512 212 562 458 777 324 214","279 0 367 67 417 179 632 45 69","512 367 0 300 434 491 649 412 298","212 67 300 0 350 246 565 112 2","562 417 434 350 0 596 215 462 352","458 179 491 246 596 0 811 224 248","777 632 649 565 215 811 0 677 567","324 45 412 112 462 224 677 0 114","214 69 298 2 352 248 567 114 0"}

    Returns: 2293

  49. {"0 41 47 61 58 66 29 20 31 12 33 33 59 60","41 0 88 35 70 62 58 61 32 51 8 74 98 99","47 88 0 108 32 40 76 67 78 59 80 80 79 80","61 35 108 0 105 97 85 81 59 49 43 94 96 97","58 70 32 105 0 8 87 78 89 70 62 91 47 48","66 62 40 97 8 0 95 86 94 78 54 99 39 40","29 58 76 85 87 95 0 49 26 37 62 62 84 85","20 61 67 81 78 86 49 0 51 32 53 53 52 51","31 32 78 59 89 94 26 51 0 19 40 64 66 67","12 51 59 49 70 78 37 32 19 0 45 45 47 48","33 8 80 43 62 54 62 53 40 45 0 66 92 93","33 74 80 94 91 99 62 53 64 45 66 0 92 93","59 98 79 96 47 39 84 52 66 47 92 92 0 1","60 99 80 97 48 40 85 51 67 48 93 93 1 0"}

    Returns: 729

  50. {"0 1019 162 1090 1077","1019 0 857 413 333","162 857 0 928 915","1090 413 928 0 427","1077 333 915 427 0"}

    Returns: 4035

  51. {"0 925 452 788 1119","925 0 473 672 331","452 473 0 1008 667","788 672 1008 0 341","1119 331 667 341 0"}

    Returns: 3052

  52. {"0 297 916 1227 1226","297 0 1213 930 929","916 1213 0 359 360","1227 930 359 0 1","1226 929 360 1 0"}

    Returns: 2502

  53. {"0 143 114 189 167 93 253","143 0 29 309 310 236 245","114 29 0 280 281 207 216","189 309 280 0 170 96 64","167 310 281 170 0 74 234","93 236 207 96 74 0 160","253 245 216 64 234 160 0"}

    Returns: 686

  54. {"0 584 1263 458 808","584 0 713 150 384","1263 713 0 863 455","458 150 863 0 531","808 384 455 531 0"}

    Returns: 4083

  55. {"0 43 12 54 5 120 43 35 63 10 58","43 0 55 32 48 155 86 61 106 53 92","12 55 0 42 17 109 35 23 61 2 46","54 32 42 0 59 123 77 29 103 44 60","5 48 17 59 0 126 48 40 58 15 63","120 155 109 123 126 0 102 94 77 111 63","43 86 35 77 48 102 0 58 26 33 39","35 61 23 29 40 94 58 0 84 25 31","63 106 61 103 58 77 26 84 0 59 65","10 53 2 44 15 111 33 25 59 0 48","58 92 46 60 63 63 39 31 65 48 0"}

    Returns: -1

  56. {"0 44 269 390 258 253 299 342","44 0 225 367 275 209 255 388","269 225 0 283 50 227 30 247","390 367 283 0 333 158 313 530","258 275 50 333 0 277 80 297","253 209 227 158 277 0 257 474","299 255 30 313 80 257 0 277","342 388 247 530 297 474 277 0"}

    Returns: -1

  57. {"0 17 26 12 27 24 34 14 21 10 24 33 20 24 24 7","17 0 10 15 11 8 18 2 5 6 12 17 16 8 15 9","26 10 0 25 21 18 8 12 15 16 10 7 26 2 22 19","12 15 25 0 19 23 33 17 14 18 27 27 8 23 30 19","27 11 21 19 0 19 29 13 6 17 23 19 21 19 26 20","24 8 18 23 19 0 26 10 13 14 14 20 24 16 15 17","34 18 8 33 29 26 0 20 23 24 18 15 34 10 14 27","14 2 12 17 13 10 20 0 7 4 10 19 14 10 17 7","21 5 15 14 6 13 23 7 0 11 17 13 21 13 20 14","10 6 16 18 17 14 24 4 11 0 14 23 10 14 21 11","24 12 10 27 23 14 18 10 17 14 0 17 24 12 17 17","33 17 7 27 19 20 15 19 13 23 17 0 33 9 28 26","20 16 26 8 21 24 34 14 21 10 24 33 0 24 31 21","24 8 2 23 19 16 10 10 13 14 12 9 24 0 23 17","24 15 22 30 26 15 14 17 20 21 17 28 31 23 0 24","7 9 19 19 20 17 27 7 14 11 17 26 21 17 24 0"}

    Returns: -1

  58. {"0 1 3", "1 0 1", "3 1 0"}

    Returns: -1

    The cost matrix is inconsistent since it says the cheapest cost to travel between city 0 and 2 is 3, even though it obviously can be done at cost 2 by making an intermediate landing at city 1.

  59. {"0 1 6 17 26 13 7 16", "1 0 5 16 25 12 7 15", "6 5 0 21 21 8 12 11", "17 16 21 0 42 28 23 31", "26 25 21 42 0 13 32 10", "13 12 8 28 13 0 19 3", "7 7 12 23 32 19 0 22", "16 15 11 31 10 3 22 0"}

    Returns: -1

  60. {"0 127", "127 0"}

    Returns: 127

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: