TransportationNetwork
Pilot 2 · 2009-09-29 · by vexorian
Pilot 2 · 2009-09-29 · by vexorian · Graph Theory, Greedy, Sorting
Problem Statement
Problem Statement
Little Johnny has just been named minister of transportation for the republic of Feudalia. Feudalia currently lacks any means of transportation between its cities, which has prompted Little Johnny to begin the planning process for a new transportation network for the twentieth century. To do so, Feudalia may build roads to connect pairs of cities and may also build airports within cities. Each airport costs airportCost to build. The construction of a road of length L will cost roadCost x L. A road must be a straight line between two cities. Although roads may cross, road travel between two cities must be done in a straight line. Air travel is possible between two cities if and only if both cities have an airport. Little Johnny requires every city in Feudalia to be reachable from all the other cities. Formally, a city B is reachable from a city A if any of the following conditions is true:
You are given the coordinates of the cities as twoint[] cityX and cityY such the i-th city will have cartesian coordinates (cityX[i], cityY[i]). You are also given roadCost and airportCost. Return the minimum cost the ministry of transportation will have to incur.
- There is a straight line road between A and B.
- Both A and B contain airports.
- There exists some city C, such that B is reachable from C and C is reachable A.
You are given the coordinates of the cities as two
Constraints
- cityX will have between 1 and 150 elements, inclusive.
- cityY will have the same number of elements as cityX.
- Each element of cityX and cityY will be between 0 and 1000000, inclusive.
- roadCost will be between 0 and 3.0, inclusive.
- airportCost will be between 0 and 10000000, inclusive.
- The locations of the cites will be distinct.
Examples
0)
{0, 0, 400, 400}
{0, 100, 0, 100}
1.0
150.0
Returns: 500.0
An optimal transportation network would be: - Build roads connecting city 0 with city 1 and city 2 with city 3. - Build airports at cities 0 and 2.
1)
{0, 0, 400, 400, 2000}
{0, 100, 0, 100, 2000}
1.0
500
Returns: 1600.0
2)
{0, 100, 200, 300, 400,2000,2100,2200}
{0, 100, 200, 300, 400,2000,2100,2200}
0.5
200
Returns: 824.2640687119285
3)
{798, 915, 797, 463, 895, 523, 959, 702, 235, 523}
{126, 25, 402, 45, 841, 762, 982, 605, 616, 78}
1.66
300
Returns: 2727.2895312339606
4)
{557802, 812498, 636233, 424085, 980711, 847114, 900568, 956336, 109742, 454851, 252456, 649901, 724152, 907568, 60846, 291044, 396668, 849073, 899079, 673201, 96746, 740557, 648083, 646514, 273886, 995783, 746359, 292092, 216020, 646783, 27569, 953256, 175107, 227461, 467811, 82047, 775304, 862184, 507874, 991745, 629922, 48943, 150625, 998549, 29882, 154611, 657533, 301326, 590992, 95980, 756693, 468022, 840720, 365862, 512594, 484015, 655662, 478932, 927426, 169927, 122021, 788135, 661953, 663493, 365958, 1209, 873670, 402940, 47833, 475871, 805595, 924881, 265062, 836278, 354962, 653992, 463498, 387170, 735991, 795722, 584200, 734919, 148996, 722570}
{544081, 982988, 398664, 181094, 278280, 806148, 542606, 395192, 687628, 985958, 930583, 31216, 612667, 145200, 538425, 397595, 543990, 864237, 738257, 105256, 339341, 24467, 55551, 827181, 777822, 72467, 352881, 401393, 935436, 981649, 218944, 324318, 150530, 580898, 381760, 919693, 895432, 946511, 988622, 468736, 732506, 390882, 298130, 57782, 891343, 621055, 313619, 234235, 179475, 52372, 466539, 217697, 361357, 387391, 26663, 870452, 2299, 789198, 597040, 867772, 776844, 103770, 320116, 183341, 714410, 48748, 465562, 792562, 385731, 188496, 870805, 336357, 981269, 830300, 916527, 208829, 871410, 813701, 143904, 735632, 121751, 402298, 315470, 67694}
2.84494669476
7.73575632097
Returns: 649.80353096148
case 1)
5)
{975128, 247226, 826801, 504273, 517615, 317268, 879838, 901026, 32216, 535569, 714565, 309367, 424375, 284104, 247230, 333512, 333836, 880526, 191644, 685229, 81595, 382943, 928298, 391784, 635736, 504375, 196456, 954982, 773056, 539935, 900381, 573018, 481247, 485499, 88300, 80615, 829682, 966193, 604591, 24540, 751779, 841541, 190714, 668234, 406216, 833538, 558811, 333986, 308653, 375379, 41617, 361459, 197415, 488906, 300161, 380633, 612054, 63364, 915166, 769706, 198882, 760903, 215565, 980275, 61714, 963103, 763347, 134809, 577855, 465689, 120169, 600793, 900595, 728997, 238677, 644839, 535507, 949996, 447834, 106357, 173417, 646066, 868798, 228976, 723432, 317940, 386521, 649975, 534244, 556871, 584599}
{916311, 806304, 40636, 666904, 70937, 976993, 67827, 590168, 733315, 918111, 921831, 737385, 569167, 82669, 882045, 281704, 121905, 554652, 69014, 710121, 654771, 928477, 133963, 362682, 702165, 530857, 456444, 574582, 325399, 560365, 805115, 411190, 449339, 319847, 496860, 278893, 616623, 986660, 199662, 132828, 426572, 964637, 219542, 671707, 853682, 982464, 580224, 413777, 568173, 213385, 592282, 14308, 976932, 157878, 41623, 10200, 276942, 129332, 979632, 566229, 748691, 951292, 260552, 60765, 708135, 93575, 694701, 115157, 812035, 157292, 751176, 533006, 170463, 853981, 844059, 870174, 487195, 187581, 700517, 294940, 313287, 374374, 126729, 221176, 567515, 555461, 749680, 642836, 708981, 784243, 820742}
2.54341708588
1.65683921121
Returns: 150.77236822011
case 1)
6)
{493290, 412712, 308787, 356857, 207666, 398346, 476937, 672932, 636810, 549412, 90315, 829953, 203975, 101073, 640835, 870633, 701969, 13666, 937002, 82927, 83519, 649489, 451696, 425373, 34606, 862681, 867586, 763256, 969592, 579838, 960640, 595723, 783333, 307985, 386914, 729480, 769946, 233043, 448963, 112063, 927856, 932362, 230611, 629203, 975372, 736629, 111801, 410890, 236429, 867592, 297242, 458120, 427819, 38433, 60426, 95661, 413876, 234158, 925619, 90564, 507312, 366991, 577574, 967120, 27223, 611276, 796058, 904937, 937155, 457589, 178183, 806732, 775714, 425513, 104310, 954029, 556553, 621188, 152468, 599984, 22176, 861440, 221111, 990373, 463389, 630121, 118, 593803, 858761, 643897, 916858, 86826, 472168, 629980, 903674, 163590, 348336, 595302}
{258090, 830820, 490910, 7608, 768668, 842151, 944813, 261304, 74186, 328011, 340737, 962629, 757432, 769269, 883622, 571994, 120841, 40807, 987632, 968112, 566037, 888566, 790054, 402209, 730291, 342939, 33881, 545102, 496446, 742220, 699300, 948337, 573131, 889608, 140090, 982227, 660305, 261615, 742106, 932595, 955237, 933651, 326813, 282697, 999244, 776708, 323812, 298551, 100754, 743717, 696415, 33175, 530718, 763007, 153914, 918229, 180565, 108838, 428623, 652780, 985775, 27068, 514091, 949504, 660105, 236185, 723842, 976621, 911634, 554997, 347975, 583411, 336841, 185972, 844698, 795883, 80015, 226619, 457737, 332436, 388294, 97881, 84905, 28365, 355098, 864868, 864986, 601681, 535902, 166911, 256585, 202332, 461250, 555905, 526729, 486339, 51393, 428976}
2.90920508696
8.87012861292
Returns: 869.27260406616
case 1)
7)
{478564, 334873, 267381, 49332, 736321, 358992, 234752, 154092, 153635, 410091, 44096, 395181, 271708, 666532, 10053, 952588, 525266, 277989, 919431, 137855, 592504, 941617, 896418, 329292, 339681, 866976, 599397, 495709, 728476, 254720, 157507, 238566, 793737, 715418, 224597, 264518, 953697, 619302, 688308, 204135, 958443, 260232, 977395, 27272, 208930, 202526, 234108, 427536, 874209, 626526, 282380, 613777, 616043, 870791, 414707, 535328, 656012, 54183, 860559, 786754, 672689, 747612, 667917, 909511, 849321, 237703, 419092, 417863, 557696, 221799, 380006, 622393, 104686, 2068, 309260, 732611, 971681, 573721, 947935, 542666, 211985, 658342, 48755, 821013, 615458, 36105, 465732, 260580, 735454, 411377, 178199, 640281, 750438, 636565, 984742, 129404, 110675, 143894, 62311, 805474, 358790, 7542, 203419, 946549, 116195, 354070, 424300, 137650, 611844, 376759, 637012, 723547, 581179, 185788, 951973, 478030, 999456, 927761, 902517, 800619, 490827, 659609, 791546, 241638}
{315923, 998442, 842028, 868436, 664693, 367854, 523877, 879014, 634059, 570835, 831022, 910556, 737497, 129334, 579167, 60749, 330546, 981236, 366436, 776840, 187251, 787015, 578594, 713259, 949105, 725571, 105511, 140999, 99145, 812272, 557701, 7880, 945862, 771534, 12135, 441081, 789017, 47514, 179663, 507151, 590821, 449054, 629946, 903363, 758798, 934916, 514174, 541714, 999510, 311606, 683332, 423554, 623411, 236304, 353139, 525919, 159405, 723229, 968076, 667726, 820629, 801509, 775722, 812813, 404943, 715570, 251864, 14643, 944038, 486284, 188296, 379608, 512196, 76089, 549523, 847869, 360058, 39976, 880403, 962950, 177005, 529506, 80087, 809677, 642553, 553608, 512561, 630821, 942333, 31938, 580260, 671994, 989458, 931138, 548226, 586190, 279812, 978899, 960436, 163358, 226097, 365885, 347921, 209225, 440873, 816178, 69076, 979062, 625302, 977279, 181239, 424903, 278094, 786854, 134052, 865291, 478938, 641937, 164680, 524713, 499921, 303298, 968909, 657990}
2.92724438743
6.56983747651
Returns: 814.65984708724
case 1)
8)
{425190, 63966, 892927, 999138, 544727, 453733, 179924, 463320, 255884, 230119, 690333, 836017, 192739, 827594, 54645, 126778, 325965, 179910, 49975, 4296, 845499, 540778, 227220, 20241, 209442, 508556, 375382, 831818, 977953, 404292, 610187, 625594, 642810, 299267, 230540, 732036, 355817, 313638, 712528, 694902, 326859, 752300, 358534, 20841, 478240, 650713, 798350, 804632, 317086, 153911, 834070, 245527, 282264, 177550, 743575, 899415, 841497, 543836, 251144, 68969, 720557, 393345, 246502, 765791, 189367, 102471, 912787, 145569, 362621, 246547, 845136, 199621, 704077, 172107, 227272, 50908, 695417, 114556, 929737, 858387, 430969, 365937, 959241, 553716, 790475, 912811, 386589, 343841, 624031, 872481, 230347, 62840, 186025, 933079, 436776, 336054, 60602, 627521, 382464, 763076, 927923, 937824, 757040, 656266, 552831, 296823, 224701, 269741, 123269, 429185, 408582, 467170, 19819, 949379, 7363, 613454, 929523, 139982, 125989, 632958, 582661, 919589, 845212, 568233, 600422, 421733, 367002, 656279, 571799, 271515, 992217, 344310, 6153, 251134, 205495, 375688, 400822, 873301, 919333, 101555}
{729640, 844959, 898673, 876767, 383924, 785247, 412868, 271437, 298582, 583753, 372268, 11270, 717932, 634366, 588853, 25242, 64470, 80091, 590581, 409531, 712854, 803623, 21989, 198608, 953749, 955888, 886401, 262357, 787934, 22683, 776837, 11014, 404800, 723423, 330747, 170985, 222242, 921095, 120755, 530268, 375888, 796414, 697963, 172961, 345933, 435176, 379844, 673238, 615281, 751490, 649109, 951364, 174930, 774580, 591082, 401412, 419660, 373490, 839704, 556970, 144329, 818418, 23961, 215650, 891102, 998773, 336958, 625243, 629903, 411370, 754436, 885473, 267924, 254479, 753012, 105713, 150321, 2185, 978778, 879286, 747122, 48730, 622135, 161413, 456020, 672427, 420265, 466973, 693863, 553119, 113689, 566886, 913525, 330963, 22342, 529364, 472131, 771778, 688134, 510529, 664018, 794049, 274443, 743924, 3729, 384051, 929089, 654320, 299019, 646922, 843379, 591922, 719944, 944648, 979200, 713775, 865716, 999101, 567369, 561307, 441457, 956379, 418913, 756168, 229360, 632101, 75457, 921459, 249795, 651820, 730173, 36224, 690749, 285889, 577224, 298097, 981873, 296997, 45371, 586329}
2.58540750374
7.143795758
Returns: 1000.1314061200001
case 1)
9)
{597063, 148492, 266975, 814597, 956784, 712195, 183122, 133684, 468061, 245790, 385183, 937797, 222242, 278438, 425219, 944602, 777079, 97598, 361226, 92895, 516306, 892996, 241642, 665164, 4808, 362371, 10292, 444435, 250945, 166984, 399393, 752316, 394743, 704189, 768207, 891493, 802600, 413688, 582489, 137850, 101576, 992034, 429864, 995056, 465540, 930906, 262694, 434339, 363693, 726383, 787724, 786658, 543283, 628374, 937176, 917911, 835593, 728855, 500116, 349628, 481305, 571965, 114078, 462095, 406593, 686356, 228553, 621701, 621296, 785427, 236771, 266374, 178081, 398527, 637078, 746715, 383609, 600758, 729070, 364915, 815962, 128006, 247465, 389559, 251301, 296799, 530013, 926714, 265030, 435491, 638890, 764531, 744742, 697459, 12074, 268523, 802304, 38258, 816437, 722723, 611931, 560806, 138741}
{280799, 780865, 324255, 125042, 439473, 751443, 905531, 379664, 376753, 918433, 838414, 381287, 614394, 551281, 159253, 406563, 367438, 282519, 660187, 979491, 917967, 130171, 573744, 175070, 551670, 779026, 339473, 995179, 585272, 978609, 333444, 543632, 525194, 454629, 186448, 753092, 350529, 366412, 328131, 423507, 710210, 534790, 634122, 152582, 910364, 717629, 822808, 817694, 26323, 713219, 121284, 586291, 375269, 421828, 903537, 325082, 256288, 556875, 728897, 715014, 285256, 847530, 974280, 5161, 207303, 535172, 519562, 725237, 71827, 788472, 835096, 331186, 381562, 207696, 943463, 520206, 128872, 810180, 779619, 439400, 885398, 387081, 49806, 593811, 506968, 805194, 209806, 823836, 548039, 205280, 549831, 195366, 686623, 30482, 112533, 184347, 596046, 300951, 468115, 259957, 652795, 291687, 232785}
2.62485614264
7.30330666057
Returns: 752.2405860387099
case 1)
10)
{886784, 356860, 214297, 28799, 337778, 203141, 777296, 522416, 303326, 603292, 766134, 706416, 201809, 600877, 16428, 515025, 484971, 184834, 667326, 587623, 307740, 798359, 968354, 605988, 721167, 953098, 891104, 653853, 378065, 544320, 572252, 734427, 730313, 642517, 890229, 43428, 829384, 307404, 197789, 965478, 85687, 30650, 48189, 901204, 478761, 144023, 489082, 857031, 397887, 396006, 449227, 536459, 330368, 301451, 261172, 450901, 221301, 853616, 669660, 197291, 600385, 727617, 246657, 794294, 279576, 508927, 521092, 507995, 211952, 64192, 503007, 709927, 808092, 610084, 935139, 70112, 184936, 499238, 972463, 56896, 640196, 161944, 392007, 649887, 618456, 898749, 162656, 741949, 432358, 920124, 660546, 725655, 549, 905696, 557648, 984135, 806516}
{9767, 185923, 964539, 804167, 752058, 36003, 544923, 767830, 563980, 225334, 721715, 487452, 264110, 89343, 430194, 857740, 152540, 58424, 721651, 855766, 765383, 408142, 6937, 998686, 125270, 116265, 37506, 797032, 639742, 536596, 677690, 682258, 210963, 780744, 294564, 679301, 198923, 759848, 706321, 583894, 929896, 842253, 330838, 199480, 807822, 249747, 815771, 668324, 945439, 272773, 442889, 271071, 697085, 716140, 644869, 373719, 63696, 421810, 456838, 96157, 368728, 78524, 371256, 27963, 51386, 549566, 431594, 488152, 105946, 134327, 940014, 659872, 268695, 424184, 831306, 874193, 262953, 800082, 50868, 675223, 841684, 582876, 26387, 808635, 351135, 364374, 577900, 63551, 900423, 241004, 486720, 796402, 697446, 738157, 773771, 5221, 977255}
2.72537783013
4.66159530071
Returns: 452.17474416887
case 1)
11)
{302640, 261388, 578887, 528061, 478980, 277399, 722455, 268741, 822213, 905760, 756575, 675732, 147520, 605370, 716543, 754913, 991554, 166339, 303785, 573218, 294077, 572562, 741821, 395571, 294684, 656012, 167066, 844560, 210796, 815091, 260352, 735394, 323744, 567731, 789893, 365746, 783696, 683405, 461305, 578242, 145841, 859536, 467405, 478228, 464567, 992557, 838850, 981471, 560306, 879459, 714427, 803144, 225689, 614176, 190996, 412400, 376812, 932099, 485718, 640537, 892475, 770076, 39844, 948215, 964810, 505877}
{900699, 792450, 337388, 593527, 952966, 599269, 891099, 655535, 435770, 926946, 898904, 527346, 847968, 568424, 900292, 818598, 957847, 742221, 756232, 245564, 671793, 602309, 184187, 864071, 621981, 606498, 967614, 979566, 317897, 589093, 366633, 560220, 463324, 77407, 936762, 369760, 643729, 170050, 248706, 810254, 502199, 112175, 454317, 630735, 345334, 596682, 253864, 179388, 403715, 749215, 123294, 723855, 377336, 311915, 725157, 175075, 942055, 864412, 318460, 347884, 229998, 299098, 22005, 802971, 710922, 256080}
2.73340323543
6.90675880089
Returns: 455.84608085874
case 1)
12)
{900411, 721192, 927071, 29971, 105908, 351220, 127071, 128774, 127784, 420759, 324505, 411601, 720282, 818391, 844663, 774500, 229178, 29335, 247760, 65055, 621902, 769064, 624211, 14731, 434688, 978894, 873532, 470583, 279417, 673123, 722870, 13321, 331972, 41182, 468968, 899944, 481645, 313485, 902303, 942808, 36459, 520972, 788750, 466800, 129617, 665441, 831687, 563295, 836719, 857334, 604694, 251321, 478995, 513363, 300251, 212535, 775395, 72841, 578727, 149221, 361081, 133776, 249917, 321880, 145003, 692900, 624936, 348550, 919314, 75934, 758110, 375358, 637113, 46520, 819438, 598081, 511195, 609036, 388439, 918972, 853146, 730362, 844988, 727327, 123782, 217356, 3441, 457263, 425705, 98677, 172781, 174361, 744331, 534736, 474375, 257520, 39634, 43606, 169773, 907209, 121158, 379750, 795402, 851214, 238341, 902223, 659028, 542969, 355872, 458278, 577092, 993439, 345014, 773756, 308890, 496659, 691471, 639767, 284253, 523908, 625862, 401709, 945495, 653941, 948657, 52166, 449508, 986108, 345887, 774814}
{718066, 27830, 588865, 469295, 305101, 826344, 277129, 358560, 560299, 320450, 967961, 986610, 782789, 457564, 220215, 154200, 63786, 155094, 532191, 789908, 803009, 403187, 952728, 327687, 334399, 323756, 228392, 96321, 874457, 227887, 388689, 435744, 810222, 690658, 319504, 325197, 273719, 541090, 215612, 580445, 520142, 982949, 756445, 759926, 831227, 909654, 504158, 312316, 931933, 73959, 383137, 418189, 21546, 450989, 927147, 650346, 782175, 268625, 141086, 647214, 312241, 392126, 932978, 614181, 559108, 709455, 330749, 258594, 64250, 138140, 295092, 431189, 493367, 163377, 830323, 837478, 489994, 77092, 902716, 691709, 154106, 454820, 580756, 543714, 344326, 456914, 803615, 365440, 321828, 964224, 166985, 744341, 42545, 885262, 578964, 353342, 890187, 426980, 525100, 424852, 83791, 520612, 446641, 68066, 576898, 834846, 827740, 824373, 490808, 528811, 152493, 526974, 777901, 62316, 649765, 719786, 961962, 883148, 496371, 919258, 644612, 640416, 817717, 242614, 398498, 322407, 655983, 313034, 305781, 301199}
2.77843534921
3.41532596458
Returns: 443.9923753954
case 1)
13)
{687812, 634530, 338885, 121839, 882367, 530733, 244826, 2508, 153590, 855411, 398983, 11926, 107078, 295439, 278827, 417582, 164056, 68138, 779986, 43764, 379374, 890156, 850298, 123070, 872521, 995450, 758122, 527209, 306971, 931888, 245628, 379961, 898031, 359809, 160742, 377398, 34203, 860938, 304589, 108480, 1475, 606134, 143052, 169112, 55509, 631625, 570258, 222125, 927042, 598894, 324030, 355910, 53397, 634313, 122597, 834174, 494044, 473284, 227465, 840110, 745063, 840395, 558733, 889367, 560079, 356076, 178838, 29351, 276181, 471329, 852308}
{545455, 838308, 978333, 931062, 865104, 330482, 31517, 809326, 805420, 89516, 927631, 313317, 691450, 572268, 899810, 864832, 853040, 974835, 656444, 726836, 137874, 102245, 749031, 332516, 607030, 37460, 297933, 791446, 377880, 275763, 487404, 686432, 995599, 406045, 99798, 977876, 68600, 309923, 409559, 925580, 9371, 624461, 339662, 426795, 256578, 601684, 204076, 188213, 468625, 920823, 729881, 736702, 615237, 187664, 35875, 789469, 163693, 188051, 559412, 960281, 816338, 546393, 541195, 89113, 595504, 670955, 425677, 503566, 742291, 507191, 447178}
2.97271793794
4.01211245785
Returns: 284.85998450734996
case 1)
94)
{599310, 149514, 726526, 897686, 733503, 442184, 711939, 867767, 887037, 222897, 885626, 384895, 487651, 868178, 422657, 419684, 706138, 285987, 716193, 267776, 295831, 225941, 90252, 531201, 455253, 106136, 371179, 252645, 709452, 714534, 804772, 840883, 660074, 545267, 474105, 486740, 636422, 500439, 689001, 180126, 636153, 462309, 199585, 469256, 256649, 60605, 115294, 522606, 636762, 583328, 358413, 77805, 557531, 663731, 845954, 235663, 491444, 634290, 279836, 654825, 760354, 984471, 173556, 403258, 942567, 633132, 202149, 352354, 274709, 225288, 998420, 854738, 982189, 297904, 130787, 904583, 651272, 111987, 696190, 888106, 905327, 357999, 121092, 26339, 988087, 497851, 304622, 99439, 483882, 999014, 305802, 849148, 14967, 585911, 695792, 372801, 545405, 695912, 873727, 432018, 949447, 959366, 218794, 378722, 776964, 785709, 1798, 284829, 280736, 602435, 892100, 91580, 500081, 22939, 603623, 414267, 217144, 687792, 566272, 329810, 804441, 115176, 649504, 671152}
{521432, 556766, 913834, 142430, 822171, 674657, 71778, 837675, 404459, 296599, 582307, 610669, 450051, 891450, 98251, 364303, 615527, 114265, 763244, 332400, 180579, 187414, 437532, 17812, 524953, 719580, 771833, 913434, 536169, 33231, 877660, 96854, 770698, 301281, 547053, 573536, 980737, 876293, 911694, 541205, 795419, 895469, 627061, 340706, 37309, 992670, 792229, 823584, 551931, 182628, 924910, 265506, 529782, 250061, 320091, 697782, 955734, 977412, 374351, 718631, 719480, 135430, 912889, 879558, 546409, 999753, 359426, 49133, 929336, 630909, 464581, 741671, 324715, 935440, 123926, 322996, 236890, 920907, 838276, 800915, 4627, 128334, 965353, 225756, 432565, 902047, 753471, 288126, 618721, 19560, 407173, 341544, 659998, 501374, 827516, 286575, 130089, 529742, 672756, 706879, 137385, 840319, 250400, 614907, 131257, 415127, 790538, 859043, 916314, 25251, 500941, 977046, 781350, 224074, 998247, 957909, 393202, 940316, 111906, 556512, 814869, 858294, 515667, 385880}
0.0
0.0
Returns: 0.0
lame case.
95)
{130082, 583667, 861659, 533111, 162605, 964949, 819465, 896802, 602720, 61436, 51751, 281632, 151023, 185022, 323462, 728612, 730375, 629628, 331397, 901958, 177765, 253810, 712139, 14341, 40662, 879173, 471269, 217138, 425477, 87778, 844799, 194294, 159918, 581763, 304580, 350003, 254056, 365942, 303845, 499761, 192130, 418906, 897236, 571767, 380430, 385781, 405547, 249256, 111292, 203520, 284714, 518421, 960337, 820759, 925168, 569821, 934069, 452743, 748662, 714939, 993637, 553044, 949911, 371891, 881424, 940508, 497794, 110152, 214133, 536663, 50821, 33163, 667466, 124651, 805465, 619249, 430496, 396420, 231932, 372519, 401841, 441843, 901489, 270839, 8417, 537445, 452130, 64481, 573193, 865211, 937748, 167423, 252244, 629286, 925755, 974211, 747254, 57705, 914054, 758868, 117235, 117832, 879250, 452730, 548449, 402319, 929852, 920958, 973011, 43679, 817707, 200757, 503597, 911129, 538272, 587151, 141350, 988901, 37899, 831764, 128174, 83585, 674376, 198581, 512347, 970382, 309387, 241668, 979049, 877895, 39308, 644217, 151921, 567216, 295701, 424234, 226430, 511325, 351859, 86869, 11879, 480566, 214586, 4578}
{426489, 917967, 905297, 344336, 672611, 398399, 777846, 100325, 369046, 163430, 887294, 75424, 503045, 482371, 49256, 309372, 823157, 318527, 133146, 512302, 153286, 311258, 427479, 279160, 619432, 879362, 352797, 862126, 640667, 616667, 992943, 902636, 788829, 890566, 843259, 452938, 506622, 333426, 746020, 367407, 510269, 163845, 780003, 485806, 497233, 3233, 216126, 139917, 741224, 72159, 779755, 915008, 668712, 631347, 405185, 13476, 259280, 210689, 124487, 320594, 696011, 970069, 853551, 625540, 143480, 871562, 145045, 718803, 693521, 66000, 962069, 77028, 652693, 155436, 297029, 228984, 444720, 310934, 908708, 515763, 415260, 98600, 916957, 902205, 908495, 603841, 644300, 304646, 76695, 293713, 351691, 68133, 382419, 700864, 342322, 753480, 463414, 310409, 645521, 958738, 961243, 278387, 144967, 679704, 862143, 758611, 478905, 223067, 930779, 740449, 819640, 335438, 192576, 997458, 674437, 607622, 973274, 37537, 316798, 679831, 870528, 485655, 196938, 718982, 357682, 352824, 918737, 934275, 196154, 743736, 781410, 128972, 371569, 550285, 771590, 581250, 21571, 613844, 705168, 147811, 146523, 233718, 803389, 140273}
0.38505828934
9435730.09219
Returns: 3210866.090321322
don't buy any airports
96)
{124448, 265790, 670786, 599218, 159648, 629451, 205737, 839761, 749688, 962877, 258842, 291204, 518467, 142368, 353793, 157711, 260344, 199803, 767059, 135108, 42932, 642623, 902993, 286743, 876766, 337547, 51710, 768620, 962104, 709726, 604168, 552218, 617235, 550826, 908676, 404395, 970070, 754339, 76429, 557588, 780984, 698504, 336834, 738964, 564393, 140609, 665543, 542321, 179278, 721830, 756675, 722429, 528567, 821462, 540504, 15293, 274703, 660629, 237263, 803, 975655, 429550, 50637, 389776, 790399, 463082, 755287, 943096, 313139, 935683, 788786, 345599, 28595, 774133, 73140, 54880, 575177, 873608, 102487, 354519, 209838, 768889, 343486, 499080, 581578, 343692, 555871, 150930, 299757, 945652, 375638, 474819, 890541, 320094, 342199, 100104, 574543, 276116, 224079, 444157, 668021, 349804, 58562, 524172, 665582, 874603, 762732, 767745, 814074, 516526, 830907, 627247, 842926, 57884, 382042, 310419, 833609, 973010, 444335, 238795, 961408, 442478, 280806, 488241, 446087, 506327, 494354, 427723, 287402}
{186158, 386315, 859887, 163876, 883954, 955900, 873850, 321484, 357802, 140549, 194101, 926370, 132531, 643540, 726761, 750894, 823494, 676764, 449540, 144297, 687057, 538152, 175636, 377467, 673546, 97454, 787786, 786321, 462230, 230709, 932879, 201243, 760761, 143315, 111895, 725498, 302948, 743083, 91242, 2383, 288820, 932938, 268537, 490554, 221200, 520566, 71907, 989328, 584178, 258095, 626645, 200898, 327287, 135169, 468952, 223172, 683653, 128389, 934917, 281901, 597785, 135117, 508131, 511685, 171967, 32878, 305385, 820245, 827293, 162436, 634508, 57942, 649960, 610598, 987896, 296953, 901014, 27346, 877691, 594254, 845291, 554982, 148492, 381016, 195679, 368451, 691128, 880564, 746516, 836789, 433414, 91494, 703693, 151997, 274222, 645876, 392434, 960565, 113260, 389906, 759599, 526714, 85227, 38222, 302446, 189811, 772350, 930770, 461467, 521970, 306984, 654661, 742343, 396, 126703, 595549, 345339, 859874, 760990, 965517, 495988, 389417, 947898, 595288, 712747, 554492, 96167, 746779, 260323}
1.241040387
9341924.33941
Returns: 9183471.787121495
don't buy any airports
97)
{31466, 509644, 195314, 49834, 962724, 669168, 772331, 727543, 389846, 426113, 978789, 227697, 505058, 189085, 763707, 375845, 358573, 540735, 978598, 829734, 34304, 554852, 160407, 213452, 296136, 901609, 181117, 220765, 17921, 325482, 311480, 280053, 656673, 79928, 677483, 571873, 281214, 267226, 424263, 24441, 215109, 164429, 341700, 112676, 963042, 497071, 819697, 26695, 456018, 608814, 867807, 384637, 161995, 190609, 710317, 402701, 353513, 610101, 648395, 508679, 985263, 715627, 753331, 810731, 290265, 377787, 887344, 546185, 785544, 904393, 658146, 494504, 139196, 132530, 349525, 57973, 553477, 353111, 485354, 249988, 355927, 444956, 509321, 500354, 816101, 845926, 479934, 185296, 260188, 410601, 463868, 852042, 426986, 875349, 88459, 552796, 948204, 200919, 182213, 259177, 189927, 128511, 897231, 898801, 340692, 765081, 349130, 434455, 93019, 86867, 783678, 326900, 955584, 168309, 869173, 720669, 806423, 298876, 734551, 798835, 515496, 24339, 585244, 865535, 685565, 52285, 611732, 922935, 191432, 151523, 583942, 55617, 770653}
{657972, 415615, 647296, 945224, 780878, 991191, 265141, 744563, 108870, 218692, 952499, 905162, 804577, 607222, 709432, 874294, 624480, 567683, 802522, 168839, 374125, 403729, 77441, 803765, 400982, 570086, 870294, 717184, 176084, 35575, 649592, 997272, 689699, 844351, 337386, 631441, 102514, 83859, 518788, 58063, 119947, 251579, 345245, 332373, 707284, 254335, 316139, 708242, 722131, 977551, 106813, 257860, 814190, 131475, 134189, 179839, 234394, 918157, 744433, 584015, 855975, 334662, 578504, 975465, 494867, 105758, 450737, 216398, 533762, 22011, 712846, 380713, 977302, 854380, 536513, 850679, 69549, 500240, 703864, 296201, 237065, 845964, 317247, 401476, 626446, 946199, 844507, 217216, 500980, 12568, 821337, 23483, 807696, 614322, 929428, 790355, 830169, 401686, 993741, 40625, 787546, 900730, 341622, 10814, 739378, 784241, 408613, 908299, 610228, 912816, 480740, 233417, 428480, 301279, 204996, 584152, 532649, 336714, 825139, 653394, 933343, 668002, 893972, 924669, 168256, 544283, 285262, 663818, 656596, 91115, 162912, 290404, 267098}
1.86097295601
9389654.9853
Returns: 1.4492246797892898E7
don't buy any airports
98)
{685792, 896981, 445417, 165968, 36242, 62245, 127949, 431, 273792, 107895, 789131, 179969, 859653, 209173, 592538, 188940, 331166, 382716, 987832, 169769, 804712, 897017, 57100, 441837, 950988, 743447, 679263, 922352, 130207, 934114, 748614, 324282, 829983, 99537, 698290, 228243, 831429, 300566, 201051, 343105, 218375, 128186, 835739, 610563, 345348, 804620, 568370, 920384, 512078, 431759, 135726, 263054, 664110, 649593, 640158, 610360, 999132, 874239, 740564, 797938, 596666, 180400, 961074, 772848, 837834, 850690, 84797, 200306, 695628, 280082, 898975, 943057, 564977, 159218, 505733, 621400, 777284, 559467, 392844, 47479, 70299, 272075, 639986, 709340, 955056, 272571, 201143, 170911, 789781, 626941, 510143, 361910, 89764, 416704, 604040, 871317, 954272}
{121180, 980222, 134154, 172948, 289859, 60483, 651523, 492105, 385139, 896751, 325722, 752035, 799621, 286248, 552828, 536033, 498716, 862564, 486571, 687850, 763777, 840716, 289880, 590345, 711231, 56617, 888591, 259246, 469241, 857726, 827572, 919415, 768865, 37555, 235667, 746843, 768037, 535035, 185140, 672809, 216504, 101670, 572728, 793122, 808263, 460368, 923154, 133298, 498211, 98796, 278691, 75022, 960965, 562898, 620528, 900111, 793412, 93840, 521374, 946132, 306398, 545968, 685768, 483027, 242414, 599555, 778867, 418760, 101971, 750351, 110781, 420730, 895284, 758394, 942624, 708148, 189978, 55059, 69180, 649643, 530003, 33336, 472517, 103908, 557128, 510692, 991485, 518216, 472469, 557087, 896546, 751288, 599805, 516575, 792099, 108261, 177525}
0.166734850722
9071536.66111
Returns: 1081924.1321889132
don't buy any airports
99)
{899244, 726255, 60517, 597366, 183583, 193688, 585081, 756896, 299418, 165893, 448603, 121232, 318279, 876947, 393124, 185996, 254063, 229994, 36109, 964188, 15294, 204538, 205995, 73265, 814193, 3394, 188811, 286862, 806258, 465337, 254186, 460626, 153876, 603923, 166891, 634912, 713747, 744386, 818529, 665746, 569096, 977325, 406022, 789793, 496999, 173691, 904047, 859306, 732788, 664278, 285737, 74833, 182043, 167916, 732714, 150824, 302519, 124760, 167363, 959402, 387402, 481837, 688036, 213954, 479760, 734095, 899986, 833590, 649942, 882562, 162488, 221224, 928624, 500959, 696184, 955452, 662678, 709019, 954641, 283131, 500719, 389649, 563626, 754795, 147677, 490317, 739022, 116720, 388387, 626045, 703841, 512107, 288073}
{183727, 739236, 808386, 385023, 712834, 256673, 258417, 655978, 391953, 489134, 659118, 341077, 511805, 836679, 458789, 277080, 797185, 728734, 784675, 300099, 272615, 24234, 392897, 394849, 332089, 445349, 761207, 626954, 641655, 423782, 789111, 279450, 756116, 971608, 389910, 976077, 669987, 638836, 116536, 133281, 589620, 4955, 773349, 28448, 59304, 415433, 167022, 155040, 195222, 680532, 749049, 327568, 320991, 844094, 830390, 935773, 123201, 372001, 885245, 409752, 354578, 30895, 248248, 579318, 951577, 647083, 173251, 760321, 107913, 343777, 450115, 471920, 4146, 276820, 483050, 339006, 147341, 308590, 240889, 276037, 984793, 437160, 526864, 21299, 782843, 14946, 533837, 690628, 183890, 629652, 345429, 310381, 625976}
1.04925927518
9394181.65258
Returns: 6393789.225528908
don't buy any airports
104)
{186550}
{944406}
2.02608295159
97672.4292457
Returns: 0.0
Don't buy anything, there is only one city.
105)
{272557}
{403746}
0.287119378458
89204.8399755
Returns: 0.0
Don't buy anything, there is only one city.
106)
{368607}
{93769}
0.689321878419
22589.568802
Returns: 0.0
Don't buy anything, there is only one city.
Submissions are judged against all 163 archived test cases, of which 23 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TransportationNetwork with a public method double minCost(vector<int> cityX, vector<int> cityY, double roadCost, double airportCost) · 163 test cases · 2 s / 256 MB per case