Connection Status:
Competition Arena > KingdomTour

KingdomTour

SRM 477 · 2009-11-12 · by keshav_57

SRM 477 · 2009-11-12 · by keshav_57 · Dynamic Programming, Graph Theory
Class Name: KingdomTour
Return Type: int
Method Name: minTime
Arg Types: (int, vector<string>, int, int)
Problem Statement

Problem Statement

The king loves his queen a lot, and he wants to take her all over the kingdom, in just a single day.

The kingdom has N cities in it. There are bi-directional roads connecting the cities such that there is a unique path from any city in the kingdom to any other city. Each road has an integral length.

The king wants to take his queen on a tour in the kingdom which starts and ends at the kingdom's capital. Since the kingdom is really beautiful, the king wants the tour to cover each road in the kingdom at least once (it doesn't matter in which direction). However, he has been informed that this might take a really long time. Hence, he has decided to build at most K shortcuts. A shortcut can connect any two cities (even if they are directly connected by a road), and the length of a shortcut is L. Since the scenery around the newly constructed shortcuts might not be so beautiful, the king has demanded that any particular shortcut cannot be taken more than once during the tour.

The cities in the kingdom are numbered 0 to N-1. City 0 is always the capital. The roads of the kingdom are described in String[] roads. Concatenate the elements of roads to get a single String. This String is a comma separated list of the roads in the kingdom in the form "A B C" (quotes for clarity), meaning that there is a road of length C connecting city A and city B.

Return the length of the shortest tour satisfying the king's demands.

Constraints

  • N will be between 2 and 200, inclusive.
  • K will be between 0 and 100, inclusive.
  • roads will contain between 1 and 50 elements, inclusive.
  • Each element of roads will contain between 1 and 50 characters, inclusive.
  • roads, when concatenated, will be a comma-separated list of roads, where each road is formatted "A B C" (quotes for clarity).
  • In each road "A B C", A and B will be distinct integers between 0 and N-1, inclusive, with no extra leading zeroes, and C will be an integer between 1 and 10000, inclusive, with no leading zeroes.
  • The roads will be such that the kingdom will satisfy the properties mentioned in the problem statement.
  • L will be between 1 and 10000, inclusive.
Examples
0)
8
{"5 0 3,5 1 2,1 7 4,0 3 8,", "6 3 2,5 4 9,7 2 3"}
2
9
Returns: 49
1)
3
{"2 1 9,0 1 3"}
8
4
Returns: 16

If a shortcut is constructed from city 0 to city 2, then the tour 0-->1-->2-->0 has a length of 16 units.

2)
9
{"5 7 1,1 7 6,3 0 7,5 8 9,", "4 8 1,1 3 10,8 2 8,6 5 10"}
3
5
Returns: 63
3)
2
{"0 1 4"}
2
3
Returns: 7

Construct a shortcut between the only two existing cities. Traverse the road once, and use the shortcut once.

4)
6
{"4 0 4,2 0 4,2 5 4,4 3 1",
 "0,1 2 10"}
2
5
Returns: 41

Make sure you concatenate the elements of roads[].

85)
200
{"0 172 6685,172 139 1360,139 188 2120,188 85 6590,8", "5 13 2114,13 96 8919,96 62 3085,62 154 9800,154", " 138 8144,138 150 1091,150 37 3774,37 195 1026,19", "5 24 8120,24 38 7253,38 107 8253,107 4 1963,4 153", " 9109,153 60 6482,60 61 5377,61 125 8088,125 132 ", "6005,132 86 4810,86 23 7067,23 31 1399,31 57 75", "44,57 117 732,117 39 2669,39 51 5213,51 158 2328,1", "58 75 4843,75 184 1265,184 84 3152,84 102 2408,102", " 22 4512,22 144 1432,144 1 234,1 16 7998,16 130 ", "1635,130 41 5703,41 166 3507,166 9 1522,9 97 89", "55,97 77 8344,77 14 8202,14 83 7133,83 70 5785,70 ", "59 8752,59 129 1634,129 177 81,177 143 946,143 99 ", "9848,99 113 4646,113 54 9480,54 167 4869,167 128 ", "6614,128 45 8876,45 127 2293,127 30 1509,30 69 2", "402,69 103 9143,103 116 812,116 135 247,135 141 6", "517,141 80 2244,80 42 4671,42 36 6251,36 111 9102,", "111 17 1828,17 115 3778,115 181 211,181 7 4577,7", " 162 5350,162 136 4496,136 94 8145,94 183 5652,18", "3 169 497,169 34 7967,34 178 5980,178 163 5048,1", "63 47 2514,47 63 7064,63 142 323,142 199 6016,1", "99 2 396,2 88 8423,88 131 3636,131 133 141,133 2", "9 1899,29 25 325,25 49 4985,49 187 3262,187 93 ", "929,93 56 3973,56 105 8695,105 90 5210,90 33 192", ",33 79 9378,79 28 8566,28 48 7971,48 91 6773,91", " 20 1556,20 194 8963,194 196 126,196 164 3287,164 ", "155 7303,155 26 1895,26 100 3670,100 55 6685,55 1", "1 4580,11 106 3581,106 191 3057,191 193 3563,193 1", "74 6272,174 168 2532,168 189 5712,189 120 4124,1", "20 109 8910,109 104 2524,104 50 8667,50 160 270", "3,160 192 1402,192 66 651,66 87 3080,87 151 6252", ",151 15 8446,15 161 9532,161 122 6481,122 5 721", "1,5 73 6876,73 176 1626,176 186 9069,186 146 6876,", "146 198 6352,198 32 8600,32 140 7611,140 175 6794,", "175 35 7133,35 152 2396,152 173 9465,173 145 45", "82,145 119 8967,119 123 733,123 10 8324,10 44 559", "4,44 137 2438,137 82 8121,82 165 5153,165 121 7", "799,121 148 2937,148 12 5686,12 58 7085,58 170 67", "0,170 52 7411,52 157 1337,157 64 3754,64 72 4114", ",72 53 9337,53 92 5448,92 76 2058,43 142 9917,101", " 63 8074,81 145 2925,74 85 786,180 49 6218,78 8", "5 8596,95 161 8157,190 66 696,98 56 6261,197 1 8", "155,159 60 4723,65 121 3783,21 88 41,6 117 9305", ",71 17 9429,149 16 3782,182 75 2148,18 106 4799,11", "4 139 1107,3 105 9716,19 132 9404,126 87 3348,110 ", "199 5918,147 50 9130,118 142 8227,156 183 6188,67 ", "103 8773,108 137 8716,179 70 1886,40 41 4978,46", " 75 9582,89 38 6032,27 161 5283,124 184 3967,134 ", "90 3254,8 162 7217,185 161 986,112 51 2817,68 12", "0 6654,171 94 7830"}
12
1675
Returns: 1135991

Huge Depth

90)
200
{"111 0 6216,9 0 823,31 9 5218,192 9 6521,80 31 368,", "63 9 9619,76 80 9496,126 31 1140,154 63 2402,82 0", " 8488,13 0 9917,153 9 7695,37 31 849,168 31 1946,", "29 80 6739,89 0 6184,38 80 9193,3 80 2178,190 9", " 89,60 111 6957,23 111 5539,175 192 6881,24 111 ", "8082,173 31 564,170 9 4642,47 31 9064,182 31 55", "22,119 63 5614,131 80 2266,101 0 9272,19 63 720", "0,107 63 4522,44 0 866,15 0 9878,116 0 591,194 9 4", "892,42 0 7534,11 31 2589,167 31 3684,54 192 879", "3,106 31 4540,28 192 5144,61 31 6788,95 80 3218,", "53 31 9289,30 63 2365,6 0 6025,164 63 1212,108 63", " 6519,112 0 7626,5 80 1127,92 9 3452,144 0 1690,14", "6 192 6100,94 63 76,85 111 2668,77 9 28,59 192 ", "2493,129 192 2721,86 9 4813,133 111 2987,150 19", "2 8946,26 80 2381,124 9 6182,64 0 237,122 111 6", "122,127 31 7108,130 0 1687,78 192 7294,163 31 4956", ",187 63 7426,41 192 2479,166 9 2313,148 63 1332,", "57 80 5600,147 63 5118,161 192 4155,18 111 8634,97", " 31 9308,81 80 4992,62 31 9503,65 31 6860,14 0 721", "6,27 9 3710,84 0 920,138 31 4722,71 31 9204,87 1", "92 3896,12 63 8442,117 63 8772,88 111 4698,172 9", " 6749,189 0 2628,135 9 3795,195 9 2727,7 192 8176,", "199 192 4793,156 63 6133,99 31 4430,90 9 6311,19", "3 0 387,48 111 8513,36 9 2498,33 63 3564,137 31 9", "096,134 0 9948,1 9 8577,143 31 9200,176 111 9595,5", "8 0 435,70 80 3382,180 9 2451,155 31 6734,115 63", " 4446,120 9 7843,136 9 5269,169 111 4214,96 80 7", "484,128 31 1482,110 0 2409,105 31 10,179 9 8253,", "160 31 8158,152 0 7140,83 9 1508,74 0 9953,145 ", "31 2140,184 192 3458,100 31 2295,8 0 9733,46 9 42", "45,174 63 4504,10 0 6283,186 0 1161,181 111 5308", ",39 80 4741,2 192 3450,158 31 4369,104 111 8506,1", "57 31 7763,196 0 7943,4 111 5579,49 80 5178,51 1", "92 7981,98 9 5032,165 192 7164,118 80 5265,132 31", " 222,142 0 3831,91 80 9794,139 80 5669,198 111 94", "01,16 9 3722,67 63 554,162 111 4181,55 9 5139,7", "2 0 6599,178 111 3883,20 0 4704,151 31 2622,43 6", "3 7133,52 63 2402,56 0 226,114 192 6894,103 111 7", "045,73 31 779,183 9 9286,21 31 4037,123 192 9881,5", "0 111 1439,17 9 5758,197 192 9605,177 192 281,19", "1 63 6662,93 63 6477,121 111 7863,79 31 8321,18", "5 0 2887,141 192 6298,102 80 2128,140 9 2297,40", " 111 2242,22 0 3541,66 0 4266,35 80 6524,113 192", " 9306,69 80 7415,125 31 313,45 111 4953,68 80 304,", "171 63 6476,109 63 2645,75 31 9077,34 192 7423,", "149 0 9195,32 192 6620,188 192 455,159 0 9993,25 3", "1 7005"}
9
1757
Returns: 1857258

Degree between 20 and 50

95)
200
{"63 15 2773,63 28 2816,63 193 6398,63 73 4278,63", " 143 2844,63 166 2561,63 179 9395,63 118 2782,63 ", "50 1660,63 151 2253,63 65 3177,63 54 9898,63 27 9", "198,63 164 8963,63 24 4140,63 106 1640,63 160 3059", ",63 89 3001,63 51 1802,63 128 9560,63 98 7179,63", " 8 572,63 23 9799,63 81 7386,63 184 5916,63 99 660", "1,63 83 251,63 93 2291,63 16 3740,63 59 8008,63", " 34 7876,63 181 9310,63 40 674,63 37 9919,63 167 ", "8806,63 87 4496,63 111 1895,63 133 9016,63 180 3", "254,63 95 5291,63 11 7925,63 25 7944,63 168 4047,", "63 136 8626,63 71 5991,63 82 5223,63 186 7766,63 1", "50 5901,63 77 8572,63 18 7730,63 38 1028,63 17 ", "1030,63 10 7527,63 90 9864,63 109 3075,63 57 80", "12,63 194 9661,63 182 3310,63 191 7058,63 112 40", "56,63 127 7391,63 171 5788,63 5 5730,63 45 2077,", "63 64 9582,63 12 8243,63 56 5278,63 62 2902,63 6", "6 9841,63 123 2343,63 14 283,63 110 5085,63 197 35", "3,63 119 1325,63 199 9392,63 74 5049,63 69 1603", ",63 115 9269,63 189 3358,63 75 2859,63 6 6418,63 ", "29 5703,63 36 9839,63 195 8570,63 86 1024,63 162 5", "943,63 177 499,63 42 9030,63 35 6767,63 20 1157,6", "3 183 7111,63 61 3880,63 30 8850,63 145 9983,63", " 4 9721,63 21 4734,63 7 4369,63 79 3928,63 9 9711,", "63 192 293,63 101 2159,63 125 1675,63 41 138,63 1", "21 3582,63 146 4358,63 120 9708,63 113 468,63 18", "7 1635,63 169 5854,63 70 5791,63 72 3956,63 173 9", "72,63 122 4712,63 170 2193,63 52 4867,63 158 984,", "63 76 1232,63 154 2680,63 149 1201,63 188 6688,63", " 117 8566,63 2 543,63 107 5443,63 3 3239,63 88 9", "331,63 144 8569,63 31 3739,63 129 7221,63 140 289", "6,63 132 6801,63 159 4561,63 39 7563,63 185 990", "7,63 60 9344,63 33 2841,63 13 7295,63 165 7774,6", "3 157 732,63 48 1793,63 116 1256,63 196 4452,63", " 47 9471,63 92 3637,63 156 1832,63 126 2598,63 ", "0 4747,63 155 3072,63 147 7813,63 163 1817,63 53", " 3080,63 172 9693,63 148 6240,63 78 4504,63 96 557", "9,63 130 4284,63 175 4445,63 55 4022,63 49 977,6", "3 97 3761,32 164 1599,198 2 3690,43 21 6759,178 1", "60 1738,105 14 1202,174 36 5681,44 69 1973,91 19", "4 8350,176 60 6724,58 92 125,134 59 509,102 40 ", "2233,103 83 8498,100 99 1644,114 184 3555,161 111 ", "7058,124 95 7587,26 29 7662,141 79 4274,67 21 68", "4,108 149 6670,80 107 139,139 143 2480,190 32 90", "4,135 40 7274,153 99 2654,22 81 885,131 17 6767,1", "37 162 4630,152 184 1499,46 12 6508,19 44 3719,94", " 136 1324,1 8 2396,104 118 3201,68 48 8158,138 6", "6 7826,85 89 4344,142 117 8422,84 190 9659"}
11
1680
Returns: 1692430

Degree above 150

99)
200
{"89 0 5126,8 0 6040,173 89 9903,29 89 8304,111 8 3", "516,36 8 8588,10 173 6977,43 173 5159,6 29 7068,4", "6 29 2536,14 111 5324,59 111 6861,163 36 6118,19", "2 36 4038,33 10 4407,129 10 7656,133 43 9825,107 4", "3 4351,98 6 7708,183 6 5471,90 46 6229,66 46 8613", ",161 14 3803,93 14 3085,159 59 6758,60 59 8541,", "97 163 4219,21 163 5157,139 192 7625,162 192 5100,", "50 33 6203,15 33 2506,177 129 3737,120 129 6953", ",184 133 7183,180 133 3875,39 107 5698,20 107 3557", ",155 98 4603,146 98 2513,74 183 9134,164 183 5203", ",84 90 9162,174 90 5507,108 66 4346,49 66 5831,18", "7 161 7220,71 161 2652,2 93 9474,88 93 8944,103 15", "9 6440,117 159 5383,28 60 7164,176 60 8574,31 97", " 8077,165 97 3059,48 21 9260,197 21 8769,188 139", " 7574,4 139 6138,63 162 6018,1 162 6318,175 50 ", "9691,199 50 3743,25 15 4965,41 15 8952,52 177 6", "180,53 177 4441,195 120 6080,24 120 9470,91 184", " 8982,32 184 4156,193 180 7726,78 180 7635,148 39", " 2907,51 39 3150,95 20 3847,116 20 4444,131 155 49", "07,17 155 7418,118 146 5373,102 146 8688,61 74 55", "89,158 74 3654,44 164 4594,35 164 8288,38 84 3315", ",170 84 8610,23 174 7836,191 174 4316,114 108 6751", ",3 108 5703,144 49 6370,171 49 8445,9 187 3284,12", " 187 7723,145 71 6822,72 71 4040,198 2 8241,153 ", "2 7524,54 88 3826,106 88 4762,70 103 6520,57 103", " 7584,189 117 9414,190 117 2612,128 28 3318,68 28 ", "2852,22 176 7776,178 176 3959,19 31 3155,134 31 26", "88,27 165 3107,86 165 2877,64 48 6476,179 48 4484", ",157 197 8295,112 197 7385,127 188 7101,11 188 405", "7,137 4 6157,79 4 5123,13 63 3786,156 63 5074,26 ", "1 7340,130 1 4355,47 175 6042,152 175 7339,100 ", "199 9610,122 199 6007,143 25 3392,7 25 3835,40 41", " 6388,76 41 4245,101 52 4057,18 52 7618,92 53 9", "031,151 53 5711,75 195 6165,186 195 7194,113 24 87", "73,30 24 9509,81 91 4286,80 91 5681,168 32 8785,1", "32 32 4973,45 193 2900,109 193 7994,167 78 8082,6", "7 78 3839,94 148 9280,65 148 4542,194 51 7305,42 5", "1 2883,142 95 7724,154 95 9887,83 116 2674,77 1", "16 4093,150 131 4992,69 131 5079,147 17 5563,5 17 ", "2525,125 118 5173,140 118 4430,141 102 4550,160", " 102 7726,110 61 4476,166 61 3724,126 158 3080,18", "2 158 3374,149 44 9390,123 44 2801,73 35 8283,13", "8 35 8919,105 38 7411,55 38 5113,196 170 7861,13", "5 170 6743,121 23 9360,169 23 8599,62 191 5296,", "82 191 3080,34 114 4829,96 114 3796,115 3 4829,8", "5 3 7180,37 144 8403,56 144 8203,181 171 5356,10", "4 171 2867,172 9 4145,16 9 4574,99 12 5145,58 12 ", "5983,185 145 5984,136 145 5007,119 72 6449,124 72 ", "3954,87 198 3466"}
70
1823
Returns: 1394010

Huge number of shortcuts required

110)
200
{"3 150 3039,3 75 147,3 100 6736,3 76 5477,3 159 1", "609,3 123 1249,3 63 7149,3 115 2794,3 70 5097,3", " 153 9960,3 163 201,3 79 7708,3 80 4915,3 8 9419", ",3 114 5533,3 171 9999,3 26 7393,3 45 3265,3 22 57", "60,3 195 2558,3 168 9095,3 92 8324,3 130 8937,3 ", "108 1265,3 23 7223,3 71 6852,3 18 2559,3 37 2497", ",3 16 5322,3 184 5664,3 151 2971,3 38 5383,3 29 ", "1166,3 17 353,3 54 4135,3 7 704,3 82 6214,3 143 7", "541,3 161 286,3 98 8848,3 19 2417,3 175 5368,3 61", " 163,3 11 3084,3 140 1231,3 32 3090,3 78 6627,3 ", "95 1544,3 160 8690,3 154 5499,3 72 5895,3 189 6147", ",3 113 6481,3 2 494,3 176 7205,3 185 2178,3 64 10", "71,3 4 7186,3 128 8007,3 144 6131,3 20 2062,3 69 2", "155,3 173 9381,3 120 3603,3 178 5671,3 182 3657", ",3 138 1343,3 104 3498,3 181 3599,3 31 9167,3 1", "01 3276,3 127 9470,3 77 6698,3 102 3247,3 135 394", "2,3 5 6531,3 164 4645,3 105 3707,3 106 7394,3 18", "0 4623,3 147 8363,3 57 3127,3 198 6293,3 167 9257", ",3 48 4991,3 43 1796,3 97 8491,3 33 6978,3 124 155", "5,3 117 5559,3 15 3695,3 137 5866,3 162 5452,3 14", "8 8281,3 81 9291,3 131 8119,3 134 3402,3 146 72", "48,3 126 1361,3 24 9551,3 10 442,3 133 1137,3 19", "3 2677,3 40 3559,3 90 1324,3 66 5199,3 109 8229,", "3 25 8033,3 46 7004,3 49 7670,3 199 4737,3 94 887", "5,3 50 4252,3 139 2916,3 142 89,3 35 267,3 165 164", "1,3 136 2043,3 34 1820,3 99 5786,3 155 4249,3 56 8", "134,3 110 7403,3 84 8986,3 59 7078,3 141 6500,3 51", " 7277,3 85 1661,3 187 6506,3 170 9405,3 53 4461,3 ", "1 7244,3 36 7133,3 166 5465,3 55 6712,3 39 9837,3", " 158 5135,3 152 8191,3 65 5877,3 44 7410,3 188 3", "168,3 118 2795,3 58 953,3 87 3145,3 179 6617,3 12 ", "1559,3 103 1422,3 192 3150,3 73 7607,3 86 8926,3 8", "3 9675,3 177 9857,3 89 4103,3 156 9049,3 27 4316,3", " 52 1409,3 157 5276,3 30 7054,3 6 5,3 129 4556,3", " 47 3682,3 21 1418,3 107 1812,3 169 2314,3 149 2", "072,3 68 9696,3 190 1941,3 174 6611,3 122 3159,3 ", "112 6131,3 145 2149,3 125 1560,3 41 308,3 191 40", "96,3 119 6193,3 132 3614,3 88 1894,3 194 4202,3 96", " 4414,3 62 296,3 116 7201,3 74 9006,3 186 6733,", "3 121 3154,3 13 255,3 28 5421,3 14 9533,3 196 751", "9,3 67 8562,3 0 3152,3 42 632,3 183 6476,3 93 781", "4,3 197 2665,3 60 5189,3 111 7080,3 9 8347,3 172", " 4094,3 91 2951"}
6
1377
Returns: 1853583

Degree 198

Submissions are judged against all 117 archived test cases, of which 10 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class KingdomTour with a public method int minTime(int N, vector<string> roads, int K, int L) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous