WarTransportation

SRM 462 · 2009-11-12 · by stone

SRM 462 · 2009-11-12 · by stone · Graph Theory

Show categories

Class Name: WarTransportation

Return Type: int

Method Name: messenger

Arg Types: (int, vector<string>)

Problem Statement

A country is at war, and one of its messenger soldiers must transport something of great importance from city 1 to city 2 using the highway system, which consists entirely of one-way highways. As soon as the soldier sets out on his mission, he is informed by an agent that the enemy has destroyed exactly one of the highways in the country. Unfortunately, it is unknown which highway was destroyed. He won't know which highway was destroyed until he arrives at the starting city of the destroyed highway. The soldier wants to use a strategy that will make the worst-case distance he has to travel as short as possible.

You are given an int n, the number of cities in the country. The cities are numbered 1 to n. The highways between cities are given in the String[] highways. Concatenate the elements of highways to get a comma separated list of integer triplets. Each triplet is formatted "a b c" (quotes for clarity), which means that there's a one-way highway of length c from city a to city b. Return the distance the messenger soldier will have to travel in the worst case. If there is a chance that he will never reach his destination, return -1 instead.

Notes

Note that there may be multiple parallel highways from one city to another.

Constraints

n will be between 2 and 100, inclusive.
highways will contain between 1 and 50 elements, inclusive.
Each element of highways will contain between 1 and 50 characters, inclusive.
When concatenated, highways will contain a comma separated list of triplets of integers.
Each integer triplet will be formatted "a b c" (quotes for clarity), where a and b are distinct integers between 1 and n, inclusive, and c is an integer between 1 and 1000, inclusive.
Each integer in integer triplets will have no leading zeros and will contain only digits ('0'-'9').

Examples

5
{"1 2 310,5 4 924,1 4 168,4 3 779,2 4 260,2 3 758,4 ","3 315,2 4 344,5 1 232,2 5 89,2 4 228,1 5 585,2 5 9","30,4 2 37,3 4 815"}
Returns: 310

20
{"10 8 490,18 14 402,17 15 430,19 16 274,18 12 599,8"," 16 184,9 12 525,5 13 533,3 10 886,19 4 413,17 5 7","33,7 2 758,20 11 872,9 1 488,14 18 799,13 5 306,16"," 5 169,20 9 962,5 11 143,2 9 138,15 18 784,15 6 26","7,3 18 106,17 15 904,9 19 561,4 3 730,15 3 43,19 1","4 185,12 14 674,10 11 308,7 6 936,14 20 973,13 3 1","11,18 19 265,14 19 896,14 2 938,3 8 393,5 19 446,1"," 10 311,15 19 702,14 18 227,9 11 547,2 3 101,12 1 ","251,8 6 309,3 19 122,13 2 709,5 6 327,10 19 469,12"," 13 39,13 6 28,12 7 479,18 8 713,18 11 485,8 18 50",",8 1 969,9 13 322,9 17 799,8 18 937,8 9 761,6 14 5","79,14 5 325,4 14 324,8 3 334,5 2 971,14 9 483,14 9"," 807,15 17 983,6 16 512,2 3 353,3 1 206,1 14 650,5"," 9 935,17 13 592,18 15 266,6 18 611,14 4 278,2 19 ","743,18 10 144,20 14 658,20 19 398,5 20 814,5 14 55","3,13 10 977,16 7 372,1 4 249,4 17 284,1 11 302,3 2","0 832,18 19 417,16 11 856,5 7 647,11 4 21,15 8 202",",12 3 849,3 16 524,3 19 653,6 11 43,8 5 862,11 2 7","52,7 9 574,14 6 433,1 8 156,1 2 63,14 5 745,14 7 1","72,18 1 250,10 7 312,12 6 396,5 8 998,8 14 478,2 2","0 883,14 20 730,9 12 924,3 5 88,7 11 696,7 12 977,","5 4 300,2 19 484,9 8 771,15 18 632,14 20 277,5 2 7","7,16 5 939,18 2 890,20 9 637,3 5 113,6 4 495,17 7 ","195,16 10 989,14 5 770,18 6 846,5 2 785,17 5 34,10"," 15 765,19 3 227,3 15 733,19 1 381,5 16 816,6 4 22","1,19 10 125,8 7 962,5 12 303,1 20 587,14 9 761,18 ","19 275,5 2 550,9 12 22,1 16 337,16 14 993,8 12 562",",4 11 80,5 15 991,7 16 162,6 1 823,18 19 601,13 15"," 454,2 15 285,3 15 833,12 2 606,4 10 449,17 13 779",",16 10 145,19 16 980,12 13 373,14 11 31,7 15 237,2","0 16 723,17 10 517,1 13 138,18 8 159,6 4 704,16 12"," 733,20 10 900,12 1 793,4 7 875,6 13 69,14 4 276,1","6 12 517,2 1 289,9 12 306,5 7 101,16 19 393,5 10 6","64,17 14 659,3 8 684,15 8 649,19 15 984,10 12 187,","14 13 879,2 13 730,20 17 988,20 12 626,12 8 516,7 ","5 901,5 7 809,20 14 488,8 4 443,3 5 914,9 18 218,8"," 12 330,9 11 207,17 2 510,14 6 898,1 4 294,2 1 600",",2 20 465,9 20 568,11 2 73,16 3 402,5 2 493,15 2 3","55,13 18 737,14 4 734,11 16 657,4 17 517,16 10 349",",20 19 448,20 1 501,4 17 343,5 13 204,10 7 166,4 1","1 215,12 5 330,5 7 26,14 3 554,4 18 201,14 17 880,","14 18 983,2 20 840,15 16 189,4 16 327,16 12 657,12"," 18 34,5 12 587,7 1 662,4 2 35,13 1 981,10 16 334,","1 15 500,8 3 213,20 18 820,7 13 771,15 17 820,20 1","3 312,18 19 892,20 15 25,6 7 686,18 8 33"}
Returns: 265

15
{"4 11 496,8 10 787,15 6 405,10 6 679,10 3 799,8 14 ","42,2 5 67,4 1 104,7 15 136,5 9 354,15 1 946,2 8 50","7,7 2 721,5 3 851,2 12 46,10 4 151"}
Returns: -1

9
{"7 2 203,4 1 724,9 6 974,9 4 271,6 4 283,9 4 653,3 ","4 224,7 9 836,8 6 515,4 7 648,9 7 269,6 3 242,5 4 ","513,5 9 839,8 2 584,6 9 872,9 2 33,6 3 269,1 4 764",",2 8 864,5 3 643,5 3 367,5 6 322,4 2 281,4 9 463,1"," 3 833,1 3 716,9 8 277,3 6 923,9 6 706,2 8 564,3 2"," 427,8 1 714,7 4 964,4 3 478,7 1 863,6 3 644,2 7 7","45,7 3 591,3 2 46,1 2 750,1 9 138,1 9 518,5 2 995,","9 2 209,6 9 192,7 4 509,2 4 452,2 3 497,1 5 246,1 ","4 735,8 9 190,7 9 70,7 9 423,8 2 376,7 1 420,1 2 5","07,2 1 133,2 9 963,9 1 697,7 9 238"}
Returns: 507

32
{"12 22 872,26 6 889,18 8 97,6 29 868,14 7 374,11 20"," 858,1 9 871,14 11 689,19 27 994,2 17 91,8 28 136,","23 21 205,23 6 716,31 11 137,2 24 623,23 3 627,9 3"," 347,31 17 678,31 3 56,8 5 24,2 12 299,17 3 8,6 25"," 525,1 24 16,7 24 952,9 10 432,12 4 782,28 9 172,3","0 9 204,2 24 29,14 3 990,16 2 155,8 6 387,31 21 10","8,24 28 451,7 4 772,30 15 87,19 10 784,6 8 536,1 9"," 663,30 22 441,11 5 578,29 13 888,15 11 916,26 2 2","47,28 8 243,7 5 993,22 23 931,13 29 706,12 29 266,","2 26 792,27 4 748,20 32 592,19 15 755,7 8 564,21 4"," 324,7 10 464,8 31 119,18 11 459,3 22 687,28 24 83","3,11 18 588,31 5 756,30 24 722,8 30 297,20 18 580,","7 25 342,30 32 20,12 17 751,22 19 68,29 14 987,29 ","25 948,32 23 529,3 20 968,20 28 533,13 15 470,8 21"," 22,13 18 885,17 30 637,31 19 687,2 15 301,29 11 6","21,8 11 747,24 13 270,31 1 297,3 13 391,25 20 579,","6 1 973,19 17 746,28 30 352,11 26 924,21 14 796,31"," 24 195,12 21 914,12 14 516,24 20 588,11 15 386,11"," 27 716,27 4 386,9 31 743,25 9 752,4 30 733,23 28 ","460,2 7 809,11 18 806,22 9 193,26 20 159,3 30 449,","30 25 484,7 1 523,14 25 699,13 29 504,26 19 724,29"," 20 194,21 30 932,26 20 668,19 13 895,25 15 741,26"," 12 157,29 18 909,6 10 788,2 17 581,1 8 254,22 5 1","85,15 24 204,1 4 99,26 18 839,19 29 347,31 14 973,","4 23 112,5 7 44,25 27 581,32 24 882,4 16 104,28 11"," 89,31 29 698,17 3 28,13 21 562,27 20 879,8 23 325",",31 28 756,27 20 246,23 19 989,8 22 268,7 17 750,7"," 16 683,13 11 164,2 5 575,21 11 310,11 8 156,6 11 ","398,25 8 572,11 28 627,1 31 138,17 12 736,32 22 32",",31 3 354,11 4 942,17 24 57,30 2 200,9 8 98,15 32 ","241,10 11 724,13 11 474,22 27 325,5 27 507,20 25 8","45,14 3 104,11 19 63,19 16 48,2 25 263,27 7 943,27"," 16 721,22 28 219,15 17 629,20 22 263,14 9 120,10 ","22 714,9 1 621,31 19 796,22 21 452,21 15 986,19 10"," 970,27 31 381,13 14 710,25 1 339,32 14 651,31 23 ","705,32 31 737,20 29 507,24 18 567,19 6 310,21 24 3","1,6 18 101,18 30 346,15 23 442,1 22 543,28 20 197,","12 19 155,28 7 831,9 21 320,14 26 972,6 8 945,23 2","0 651,21 14 65,11 7 818,32 14 925,19 10 384,27 8 6","16,3 28 936,17 21 259,22 28 556,12 16 206,32 29 27","0,10 3 439,9 16 363,27 26 98,32 30 380,10 24 716,1","8 27 23,9 11 612,3 32 863,6 11 878,3 11 354,9 20 7","33,23 29 260,10 23 781,11 22 450,23 32 450,10 17 7","56,24 25 166,13 26 177,23 7 323,1 17 91,21 29 298,","17 24 867,7 13 237,29 30 635,28 7 452,12 10 940,4 ","23 390,30 3 703,30 26 894,1 26 790,11 14 770,12 30"," 9,22 5 381,11 1 203,21 28 473,9 7 851,20 10 745,2","5 7 260,24 5 189,29 5 350,18 15 124,3 27 809,11 16"," 205,32 26 21,18 15 192,10 23 142,12 10 423,5 2 27","0,32 25 210,20 21 566,1 6 780,28 8 446,21 19 838"}
Returns: 829

36)

3
{"1 2 1,1 3 2,3 2 3"}
Returns: 5

The best strategy is to take the path 1->2 if the first highway is not destroyed. Otherwise, take the path 1->3->2.

37)

8
{"1 3 1,1 4 1,3 5 1,4 5 1,5 6 1,6 7 1,6 8 1,7 2 1,",
 "8 2 1"}
Returns: -1

If the highway from city 5 to city 6 is destroyed, the messenger can't finish the transportation.

38)

4
{"1 3 1,1 3 2,3 2 1,1 4 1,4 2 1"}
Returns: -1

No matter what strategy the messenger adopts, there is a chance that the transportation can't be finished.

39)

4
{"1 3 1,3 2 1,1 4 1,4 2 1,3 4 1"}
Returns: 3

The best strategy is to move to city 3 at first.

69)

100
{"1 3 1000,3 1 1000,3 4 1000,4 3 1000,4 5 1000,5 4 1","000,5 6 1000,6 5 1000,6 7 1000,7 6 1000,7 8 1000,8"," 7 1000,8 9 1000,9 8 1000,9 10 1000,10 9 1000,10 1","1 1000,11 10 1000,11 12 1000,12 11 1000,12 13 1000",",13 12 1000,13 14 1000,14 13 1000,14 15 1000,15 14"," 1000,15 16 1000,16 15 1000,16 17 1000,17 16 1000,","17 18 1000,18 17 1000,18 19 1000,19 18 1000,19 20 ","1000,20 19 1000,20 21 1000,21 20 1000,21 22 1000,2","2 21 1000,22 23 1000,23 22 1000,23 24 1000,24 23 1","000,24 25 1000,25 24 1000,25 26 1000,26 25 1000,26"," 27 1000,27 26 1000,27 28 1000,28 27 1000,28 29 10","00,29 28 1000,29 30 1000,30 29 1000,30 31 1000,31 ","30 1000,31 32 1000,32 31 1000,32 33 1000,33 32 100","0,33 34 1000,34 33 1000,34 35 1000,35 34 1000,35 3","6 1000,36 35 1000,36 37 1000,37 36 1000,37 38 1000",",38 37 1000,38 39 1000,39 38 1000,39 40 1000,40 39"," 1000,40 41 1000,41 40 1000,41 42 1000,42 41 1000,","42 43 1000,43 42 1000,43 44 1000,44 43 1000,44 45 ","1000,45 44 1000,45 46 1000,46 45 1000,46 47 1000,4","7 46 1000,47 48 1000,48 47 1000,48 49 1000,49 48 1","000,49 50 1000,50 49 1000,50 51 1000,51 50 1000,51"," 2 1000,2 51 1000,52 53 1000,53 52 1000,53 54 1000",",54 53 1000,54 55 1000,55 54 1000,55 56 1000,56 55"," 1000,56 57 1000,57 56 1000,57 58 1000,58 57 1000,","58 59 1000,59 58 1000,59 60 1000,60 59 1000,60 61 ","1000,61 60 1000,61 62 1000,62 61 1000,62 63 1000,6","3 62 1000,63 64 1000,64 63 1000,64 65 1000,65 64 1","000,65 66 1000,66 65 1000,66 67 1000,67 66 1000,67"," 68 1000,68 67 1000,68 69 1000,69 68 1000,69 70 10","00,70 69 1000,70 71 1000,71 70 1000,71 72 1000,72 ","71 1000,72 73 1000,73 72 1000,73 74 1000,74 73 100","0,74 75 1000,75 74 1000,75 76 1000,76 75 1000,76 7","7 1000,77 76 1000,77 78 1000,78 77 1000,78 79 1000",",79 78 1000,79 80 1000,80 79 1000,80 81 1000,81 80"," 1000,81 82 1000,82 81 1000,82 83 1000,83 82 1000,","83 84 1000,84 83 1000,84 85 1000,85 84 1000,85 86 ","1000,86 85 1000,86 87 1000,87 86 1000,87 88 1000,8","8 87 1000,88 89 1000,89 88 1000,89 90 1000,90 89 1","000,90 91 1000,91 90 1000,91 92 1000,92 91 1000,92"," 93 1000,93 92 1000,93 94 1000,94 93 1000,94 95 10","00,95 94 1000,95 96 1000,96 95 1000,96 97 1000,97 ","96 1000,97 98 1000,98 97 1000,98 99 1000,99 98 100","0,99 100 1000,100 99 1000,100 2 1000,2 100 1000,1 ","52 1000,52 1 1000"}
Returns: 148000

max (?) answer

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

Coding Area

Language: C++17 · define a public class WarTransportation with a public method int messenger(int n, vector<string> highways) · 76 test cases · 2 s / 256 MB per case