10702 - Travelling Salesman

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10702 - Travelling Salesman

Post by brianfry713 » Tue Jun 19, 2012 2:43 am

You're assuming the starting city is always #1.
Check input and AC output for thousands of problems on uDebug!

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 10702 - Travelling Salesman

Post by @li_kuet » Tue Jun 19, 2012 5:28 pm

Thanks brianfry :D:D:D

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10702 - Travelling Salesman

Post by brianfry713 » Wed Sep 11, 2013 9:55 pm

Input:

Code: Select all

16 15 6 677
0 142 649 540 587 453 456 565 697 392 926 41 250 69 455 121
545 0 834 507 984 232 387 850 4 547 296 859 783 362 235 693
690 728 0 341 229 314 145 36 230 842 427 155 234 677 575 689
149 471 522 0 655 455 105 42 304 461 940 951 319 722 312 905
766 353 632 458 0 933 297 603 968 526 796 747 32 29 423 959
717 571 429 590 578 0 235 695 619 539 155 910 489 825 631 153
729 749 505 712 206 790 0 8 160 757 533 955 855 916 984 277
874 52 848 303 994 425 537 0 40 395 427 546 304 268 722 286
772 450 386 628 513 592 417 520 0 751 526 404 58 380 319 393
9 193 796 208 847 789 632 735 180 0 378 514 725 33 781 446
670 904 247 56 531 759 999 300 630 101 0 825 33 158 556 352
902 564 896 698 771 94 838 754 828 18 483 0 341 94 515 473
892 537 376 138 944 259 249 294 558 878 746 734 0 263 904 289
614 157 853 861 854 975 954 692 729 781 61 211 474 0 154 78
298 397 966 26 887 261 284 135 554 193 364 299 926 626 0 554
566 591 711 770 451 916 745 404 607 825 537 19 387 362 525 0
1 4 5 10 11 16

5 4 1 723
0 293 946 863 9
597 0 140 986 150
58 577 0 212 827
379 128 923 0 135
86 99 23 105 0
3

7 5 4 920
0 452 352 476 667 360 72
806 0 346 573 215 274 137
394 652 0 264 316 786 701
767 160 157 0 604 543 137
256 289 390 393 0 718 449
571 521 152 398 187 0 512
821 345 209 393 559 834 0
3 5 6 7

17 14 7 60
0 554 182 956 93 45 776 437 605 520 995 438 401 299 275 896 918
249 0 92 303 734 797 291 410 990 886 726 572 874 111 602 432 17
135 739 0 109 180 866 545 136 738 891 574 138 189 200 385 458 800
477 112 533 0 625 754 295 966 640 20 537 865 131 490 649 147 976
387 607 507 605 0 503 643 342 393 216 831 934 767 215 743 918 43
855 450 19 608 96 0 984 599 468 872 464 598 713 112 96 689 850
54 195 806 556 837 147 0 948 404 329 233 522 544 976 439 586 830
241 605 789 336 940 388 803 0 812 851 752 876 314 199 916 163 604
111 969 159 299 467 459 55 796 0 43 576 691 18 367 628 199 959
584 988 646 524 727 801 687 929 904 0 914 242 103 830 756 58 940
76 217 590 543 675 644 690 69 572 732 0 87 290 359 637 248 943
976 893 818 702 693 504 630 597 417 223 51 0 598 979 108 889 54
676 479 948 702 474 989 771 397 720 209 686 431 0 845 285 725 173
178 542 226 222 397 208 170 165 430 572 763 760 32 0 651 166 59
481 113 761 955 454 883 351 525 91 389 955 287 673 679 0 459 202
572 685 776 968 244 297 485 673 869 247 433 252 249 598 310 0 730
62 70 684 867 952 386 392 394 126 698 681 799 729 491 352 652 0
2 3 6 7 11 12 16

15 2 10 839
0 456 281 452 199 675 577 248 707 727 328 197 79 980 724
557 0 951 493 332 406 287 327 107 865 573 408 40 481 439
629 458 0 152 436 90 603 986 764 180 233 822 258 561 19
336 892 94 0 245 842 938 576 247 577 255 705 441 827 112
481 659 550 461 0 468 54 248 558 656 233 673 187 817 495
797 729 865 132 620 0 310 376 461 247 304 59 823 558 763
616 736 227 96 395 128 0 908 862 181 155 419 189 387 444
727 555 938 523 284 154 7 0 903 463 382 716 61 37 774
236 594 889 851 682 115 298 76 0 594 205 289 775 711 60
315 449 503 41 3 440 564 286 945 0 922 189 407 303 904
467 692 29 702 285 917 904 318 383 201 0 745 329 405 34
103 115 93 417 915 947 809 918 738 724 203 0 682 645 743
88 300 998 906 991 27 960 627 295 863 945 30 0 64 689
358 820 74 812 287 166 228 201 464 388 118 201 112 0 673
882 756 415 321 55 413 579 45 791 538 24 437 400 968 0
1 2 3 4 6 7 10 11 12 15

6 3 3 952
0 213 473 63 601 943
263 0 712 615 497 819
381 817 0 226 793 747
270 935 284 0 645 372
36 612 837 850 0 620
12 836 701 997 108 0
1 4 5

16 2 8 708
0 886 671 57 850 860 259 469 871 94 521 219 554 171 780 134
884 0 293 8 211 869 496 682 264 716 673 235 729 411 476 29
785 362 0 699 841 211 558 99 31 780 545 903 999 98 73 130
583 308 423 0 942 518 291 789 551 906 504 576 141 233 986 968
261 770 681 311 0 963 891 869 413 273 648 309 175 998 406 600
128 340 907 550 281 0 425 192 69 327 450 573 902 590 157 888
909 769 9 590 79 971 0 480 947 736 105 947 44 631 296 802
230 423 141 489 324 774 265 0 868 194 591 317 766 493 258 274
732 166 42 92 755 121 415 587 0 419 150 43 717 193 673 13
346 255 787 487 743 463 612 359 330 0 805 949 998 923 793 607
196 876 772 590 968 879 710 382 817 480 0 531 859 197 75 531
561 421 137 699 259 231 161 870 589 842 26 0 890 839 948 34
445 496 910 569 85 877 447 146 610 263 977 140 0 473 525 566
355 85 338 492 784 596 74 296 817 15 138 843 904 0 976 142
289 773 637 198 341 73 426 139 570 35 753 547 174 225 0 71
92 931 156 429 422 291 377 496 586 545 510 75 387 765 51 0
3 5 8 11 12 13 15 16

16 5 4 875
0 460 389 629 836 884 566 732 745 641 119 861 43 351 265 217
219 0 867 435 512 895 791 375 957 899 783 544 583 614 575 549
952 34 0 937 580 221 172 146 952 268 138 422 128 180 124 393
748 343 259 0 182 206 505 324 580 461 222 715 357 156 680 931
704 632 316 993 0 563 536 164 60 839 432 197 613 559 728 736
303 827 430 914 360 0 988 418 683 567 879 256 633 235 411 313
517 467 296 832 459 858 0 719 974 918 557 405 466 521 316 194
609 970 372 38 883 732 25 0 301 414 944 531 670 928 117 432
592 633 250 887 464 60 97 182 0 34 366 90 790 831 963 105
376 571 427 100 960 309 831 337 961 0 596 280 491 617 559 959
49 151 591 650 389 406 710 837 587 743 0 202 29 884 385 991
341 112 561 767 211 520 75 41 208 388 637 0 487 878 253 398
189 653 548 779 303 288 185 12 125 123 106 326 0 503 989 62
845 329 174 405 447 384 277 522 777 484 909 765 323 0 138 369
720 326 22 619 457 676 906 993 39 382 467 496 60 970 0 836
121 814 517 294 571 963 30 199 484 806 34 744 570 708 234 0
5 6 12 14

20 19 7 478
0 432 21 47 818 764 616 525 997 554 304 908 864 52 626 202 58 337 577 446
514 0 448 892 12 154 459 323 376 672 909 560 913 340 932 312 157 696 927 34
44 832 0 337 303 48 740 281 249 798 617 825 243 130 272 134 493 425 945 815
152 616 723 0 64 880 415 995 191 923 690 470 956 86 301 644 740 348 384 20
948 181 636 773 0 423 117 44 908 609 821 852 776 972 819 850 35 699 616 30
241 539 71 710 846 0 508 363 842 248 62 225 267 10 757 903 782 531 371 177
438 980 997 290 107 321 0 108 956 707 158 572 88 751 462 159 812 659 666 526
500 265 588 76 532 597 184 0 786 730 714 156 258 504 135 607 145 593 927 604
549 633 762 472 721 864 285 231 0 675 295 248 201 795 513 140 222 44 88 758
829 817 471 984 426 326 471 32 470 0 63 958 74 963 943 187 786 663 50 422
245 76 717 492 628 511 4 767 84 399 0 854 841 579 22 664 563 448 989 385
479 811 799 437 884 114 731 422 899 393 471 0 321 989 898 37 480 526 899 836
292 334 234 146 175 813 167 838 727 966 178 463 0 445 988 261 233 223 374 963
644 625 707 466 297 695 364 333 526 889 583 361 180 0 916 947 677 442 111 196
631 837 161 809 299 957 148 911 189 371 637 503 366 613 0 209 832 909 903 547
593 429 435 175 141 966 442 87 995 884 197 190 514 385 702 0 674 35 659 174
298 199 896 934 702 261 546 910 444 806 165 990 398 945 776 924 0 437 742 717
524 88 600 72 277 466 809 330 491 843 988 664 140 539 559 425 240 0 820 322
501 263 127 665 605 876 961 380 151 398 473 868 273 560 819 344 188 284 0 152
518 775 347 857 790 486 395 349 911 986 168 584 487 782 711 151 738 938 112 0
5 8 9 10 15 16 19

9 6 6 762
0 262 888 326 119 677 163 865 25
425 0 851 544 9 689 678 71 839
415 8 0 302 884 448 162 826 755
646 31 233 0 474 423 994 453 685
881 130 155 909 0 292 19 934 717
221 477 725 909 154 0 147 100 921
154 753 804 954 267 629 0 60 912
659 292 385 82 637 189 118 0 869
318 272 778 610 642 63 678 215 0
2 3 5 6 7 9

12 10 5 766
0 759 413 945 192 50 133 309 270 803 932 47
412 0 574 461 441 788 1000 194 262 396 445 188
712 201 0 218 831 911 514 579 680 73 690 92
17 881 493 0 502 542 115 304 473 513 67 398
974 507 185 325 0 52 799 720 848 338 783 48
555 613 958 68 544 0 637 140 233 81 509 465
925 10 358 391 665 183 0 904 731 580 877 589
117 201 992 915 272 839 604 0 54 886 158 666
844 577 561 832 68 145 264 576 0 962 541 937
319 931 601 501 834 683 433 62 623 0 549 262
614 815 885 804 418 938 690 927 956 885 0 503
868 68 570 13 332 498 974 224 434 644 154 0
3 4 8 9 12

5 5 2 701
0 15 657 643 899
813 0 412 189 502
338 496 0 738 192
363 805 113 0 727
488 610 700 63 0
1 5

12 4 10 49
0 66 705 817 919 394 312 8 585 26 812 697
105 0 652 659 804 714 54 499 282 187 690 541
388 809 0 553 985 108 578 590 401 854 7 105
670 277 498 0 333 284 434 711 447 483 815 450
141 970 164 194 0 821 797 380 510 690 119 671
242 455 130 171 44 0 531 377 402 635 398 678
133 731 313 918 793 760 0 400 607 209 540 928
724 85 748 873 816 258 914 0 287 280 507 741
409 677 137 939 53 890 926 803 0 568 58 885
232 327 677 343 727 635 904 618 562 0 627 703
310 851 870 919 116 156 198 622 897 606 0 651
385 897 55 274 822 857 193 231 741 425 557 0
2 3 4 5 6 7 9 10 11 12

19 15 10 672
0 997 589 415 853 782 997 946 558 906 714 676 540 117 698 792 81 698 98
354 0 548 274 897 866 957 285 158 536 982 99 851 576 95 791 342 300 572
339 597 0 481 244 310 157 135 426 206 927 858 903 24 211 802 649 459 20
605 95 177 0 140 77 627 342 4 722 133 345 373 56 35 969 889 630 278
397 765 56 602 0 43 913 504 418 476 657 67 934 676 671 29 852 163 457
479 856 460 552 340 0 156 276 396 543 244 284 172 873 32 288 280 633 330
193 488 748 20 144 166 0 953 820 188 333 23 702 789 853 558 600 404 897
108 31 644 650 274 279 821 0 499 310 461 778 294 790 970 781 889 341 277
54 646 96 594 978 470 295 119 0 323 204 70 78 101 177 109 96 826 734
375 999 232 36 459 10 330 600 331 0 462 841 672 738 246 317 185 839 646
7 134 116 329 337 186 758 789 362 218 0 237 540 304 963 890 887 998 348
896 679 299 579 493 491 602 230 737 270 767 0 927 915 773 412 31 453 101
568 562 889 281 132 125 820 435 439 709 321 437 0 408 569 467 59 499 959
549 100 541 637 721 307 564 635 431 975 17 235 75 0 936 796 316 217 927
792 36 713 231 97 34 667 504 954 485 914 452 444 463 0 903 984 99 623
642 14 257 424 989 626 658 415 913 453 730 129 732 522 517 0 444 752 613
829 770 468 782 254 382 233 49 196 487 384 646 109 377 660 366 0 800 1000
343 457 414 255 262 496 736 993 17 252 788 120 216 617 241 683 750 0 846
416 335 895 963 821 630 961 930 7 972 647 806 971 341 615 736 947 228 0
3 8 10 11 13 15 16 17 18 19

13 12 6 355
0 265 935 31 225 864 389 196 862 547 166 202 513
253 0 149 740 484 182 311 434 115 21 504 614 348
165 148 0 128 320 98 890 73 362 176 456 586 392
844 133 253 0 390 650 807 902 902 307 641 737 488
303 171 602 324 0 26 568 23 190 715 150 862 164
39 934 877 566 389 0 814 957 233 946 210 974 595
16 228 497 674 220 585 0 161 523 755 115 846 132
682 868 322 748 369 183 912 0 759 468 140 324 857
954 281 441 899 842 414 494 209 0 993 342 882 213
926 42 735 33 156 932 164 189 151 0 485 937 519
19 200 277 487 339 600 695 292 232 135 0 191 73
900 36 281 893 377 162 105 302 204 191 334 0 711
474 850 900 624 686 188 494 705 739 122 543 77 0
1 5 6 8 11 12

11 4 5 58
0 679 726 512 365 789 337 214 688 312 899
227 0 805 955 965 926 497 393 351 85 465
655 807 0 727 383 781 376 744 646 753 915
968 784 992 0 831 148 780 168 713 819 479
963 45 636 270 0 361 913 118 754 263 203
570 269 361 297 652 0 141 24 395 787 129
661 106 912 5 288 411 0 136 455 475 955
286 437 351 273 706 712 185 0 176 817 800
378 386 68 738 34 71 231 410 0 818 369
890 830 474 153 834 113 563 970 568 0 389
276 205 825 626 829 883 689 13 58 505 0
6 7 8 9 10

4 3 3 391
0 106 37 119
474 0 926 301
299 78 0 134
412 992 455 0
2 3 4

16 4 7 627
0 319 159 598 144 84 898 795 514 31 206 505 486 888 237 567
126 0 793 922 840 935 318 918 134 218 160 119 712 985 331 833
112 1 0 991 709 145 75 606 939 940 636 496 796 473 735 32
40 860 176 0 313 699 110 630 968 243 199 480 713 262 464 396
95 575 396 85 0 283 892 511 240 830 450 876 677 598 700 411
629 91 270 157 404 0 320 618 385 640 213 936 119 925 197 582
672 291 509 68 728 143 0 959 238 383 141 40 610 817 637 309
580 617 400 201 125 155 521 0 743 539 512 955 474 630 231 23
563 903 313 71 322 40 214 632 0 630 596 772 21 205 941 9
865 872 977 616 72 102 770 944 196 0 661 455 502 134 84 732
156 647 986 821 69 659 212 282 291 193 0 229 414 213 785 706
573 650 577 550 265 649 3 387 592 198 47 0 47 51 532 482
134 40 128 120 212 197 778 423 830 420 968 59 0 834 180 843
539 105 844 468 654 109 116 8 847 59 557 893 105 0 607 424
587 740 815 66 211 26 614 989 449 444 760 416 854 593 0 947
48 484 51 892 951 56 352 418 63 198 476 971 90 933 577 0
1 4 7 9 12 14 16

10 1 3 290
0 550 923 571 597 406 973 488 708 381
839 0 477 795 388 953 766 477 885 694
694 755 0 362 373 42 241 781 943 459
638 639 437 0 261 540 360 831 489 117
156 328 177 888 0 519 653 682 906 605
799 383 841 493 76 0 595 854 800 637
94 580 931 905 217 922 0 341 830 461
52 12 301 169 167 629 345 0 406 147
349 88 404 954 238 786 794 730 0 213
741 936 364 729 381 296 659 285 864 0
2 3 6

16 10 2 729
0 340 387 277 80 322 992 160 702 639 819 987 503 102 964 547
846 0 992 603 891 189 826 915 81 806 438 322 873 364 868 529
75 560 0 915 703 639 588 695 151 290 333 969 628 187 70 943
734 268 934 0 688 158 474 865 424 907 670 861 580 894 224 800
775 651 359 689 0 705 349 277 399 499 918 84 819 897 270 241
839 355 508 124 395 0 665 598 259 440 856 281 301 435 174 876
234 948 878 944 989 583 0 293 617 333 791 534 416 962 430 38
202 620 744 709 743 138 725 0 340 397 164 547 677 816 334 202
44 567 502 921 863 842 855 155 0 458 188 297 343 955 258 124
992 459 743 88 519 485 225 595 177 0 973 111 723 1 926 56
203 321 975 56 594 837 897 448 343 706 0 987 639 48 942 249
171 285 59 913 372 578 749 597 172 925 921 0 282 1000 922 560
407 476 232 381 531 825 569 779 273 911 484 611 0 902 883 552
150 53 837 208 317 208 137 65 156 661 342 77 942 0 341 998
853 747 825 85 480 355 261 48 485 533 311 320 496 212 0 202
47 713 606 235 920 274 443 57 338 950 69 31 26 362 723 0
12 13

19 10 7 577
0 718 965 181 667 33 211 693 746 934 419 960 107 618 962 759 874 873 458
615 0 20 820 674 662 744 287 350 733 504 273 641 995 990 957 527 657 341
737 701 0 86 22 119 46 128 88 359 886 962 231 696 928 602 867 601 263
962 239 613 0 694 743 237 334 89 227 290 615 235 630 703 935 716 77 405
113 204 493 471 0 442 806 54 489 733 7 707 685 270 668 924 234 714 18
470 399 458 48 41 0 72 282 670 126 568 737 202 325 201 758 817 24 551
974 429 39 706 435 745 0 742 56 764 665 289 477 34 111 876 491 510 916
914 144 937 40 711 26 593 0 35 578 350 203 953 252 528 381 290 585 168
386 327 223 150 343 864 978 377 0 326 205 867 835 472 781 978 409 172 41
786 764 427 715 466 630 668 717 157 0 48 7 94 215 744 420 790 245 762
5 223 138 330 427 5 516 899 137 494 0 659 308 886 796 71 312 510 888
293 177 605 450 577 611 543 143 706 314 284 0 951 75 288 173 565 617 951
921 133 201 57 978 211 364 863 6 786 174 868 0 674 467 396 630 268 972
592 162 467 297 827 750 247 901 390 771 465 6 74 0 737 490 274 793 819
485 508 33 842 646 207 709 671 25 105 300 644 428 891 0 157 246 187 983
996 786 235 385 908 52 742 981 788 584 255 581 754 91 88 0 787 284 85
345 993 755 721 449 54 364 228 296 872 474 835 854 821 620 88 0 557 527
139 298 860 927 233 466 859 339 908 298 125 191 383 469 183 137 541 0 983
543 904 211 838 775 684 24 980 504 643 67 412 522 558 61 733 836 294 0
1 7 9 10 11 17 18

13 13 8 737
0 593 849 57 617 828 912 611 246 323 484 803 384
216 0 638 29 765 331 12 221 674 119 516 46 46
345 907 0 513 508 662 587 882 607 435 938 575 262
202 537 859 0 876 373 14 259 940 651 639 705 334
650 925 359 768 0 792 404 165 488 663 29 996 676
615 877 282 49 166 0 208 662 719 745 873 595 117
886 205 56 888 844 112 0 573 493 37 931 613 180
335 777 668 349 806 663 24 0 772 891 306 821 408
513 834 127 609 706 73 725 591 0 277 133 479 120
244 51 965 632 334 577 812 668 705 0 479 16 862
493 39 634 383 696 806 142 561 639 268 0 169 697
692 246 639 969 730 469 440 973 872 756 957 0 205
684 120 872 389 950 239 602 442 629 235 176 325 0
1 4 7 8 9 10 11 12

6 5 1 217
0 717 948 731 186 740
56 0 57 495 364 261
179 483 0 484 567 432
74 168 225 0 702 755
400 378 146 68 0 614
528 356 19 958 336 0
6

11 1 5 914
0 317 138 140 836 362 841 590 113 219 88
532 0 832 967 240 202 925 575 574 951 561
28 514 0 287 537 485 507 409 68 905 115
134 221 604 0 625 56 965 465 998 429 35
85 960 219 403 0 199 772 327 125 345 629
38 724 494 324 612 0 330 830 372 397 86
486 882 306 441 506 713 0 405 323 710 833
357 146 145 927 549 343 699 0 227 820 395
208 857 119 701 180 82 31 361 0 454 779
446 291 661 103 732 518 815 488 840 0 525
321 549 670 817 475 570 511 525 797 330 0
3 4 5 6 9

16 12 9 484
0 586 667 457 486 688 625 312 258 136 837 406 817 108 409 355
849 0 464 71 671 902 852 947 118 725 865 346 53 514 91 195
650 28 0 861 459 513 548 83 825 157 570 13 562 387 120 322
741 968 786 0 163 990 39 14 288 156 91 152 853 143 17 943
337 667 971 549 0 477 835 448 911 659 605 481 671 518 867 142
840 959 461 977 121 0 451 15 487 738 522 577 890 374 71 258
668 759 924 990 307 752 0 825 106 663 835 62 495 506 580 713
647 419 671 108 395 143 910 0 761 629 647 282 205 888 655 627
146 674 385 421 664 691 173 840 0 797 187 674 210 681 531 789
393 530 559 63 989 305 557 898 65 0 186 896 346 742 784 352
369 281 26 105 701 41 796 225 880 944 0 411 905 153 443 436
294 835 317 852 249 305 157 806 202 221 343 0 449 919 436 232
270 156 864 647 261 917 39 408 141 270 703 904 0 175 207 346
962 500 533 278 704 781 582 212 938 135 432 632 583 0 702 68
167 972 223 382 970 835 298 9 242 791 278 296 694 804 0 503
391 765 354 923 394 57 56 975 620 993 461 52 625 396 105 0
1 2 3 6 8 10 13 14 15

12 6 7 274
0 196 818 955 901 741 349 310 796 675 929 140
488 0 332 116 883 437 159 796 864 129 90 261
933 34 0 18 330 416 405 23 843 947 570 13
901 471 753 0 601 132 900 628 60 391 467 392
507 349 180 17 0 496 43 497 937 656 429 971
25 759 738 781 781 0 933 727 351 945 980 173
49 580 304 300 559 715 0 690 25 458 548 725
637 917 220 680 413 157 687 0 842 479 711 952
216 492 732 500 570 434 444 549 0 958 844 129
613 143 39 328 185 416 785 732 140 0 422 648
712 453 413 220 491 254 698 553 557 265 0 44
640 765 614 74 560 162 383 404 642 996 898 0
1 2 4 7 8 11 12

13 12 8 248
0 79 738 183 474 378 299 439 803 210 953 537 965
946 0 532 863 330 206 296 777 17 813 68 600 330
717 636 0 906 586 513 440 503 943 529 37 769 258
687 207 60 0 897 511 597 861 457 480 75 786 38
723 915 406 535 0 982 5 216 50 992 122 987 857
913 842 799 441 878 0 567 699 917 126 110 813 636
58 25 92 890 452 230 0 279 174 496 684 60 829
40 276 878 384 749 217 240 0 13 58 38 453 287
957 503 203 82 965 15 717 374 0 392 161 263 843
742 893 16 237 928 427 417 968 54 0 646 351 802
862 590 814 919 979 619 206 935 473 408 0 16 789
775 85 163 166 245 777 8 986 670 375 574 0 597
153 990 916 207 635 266 360 849 207 174 767 538 0
1 2 4 6 8 9 12 13

7 1 6 990
0 23 520 695 382 505 716
756 0 430 313 260 419 228
466 405 0 846 826 253 404
351 372 293 0 846 695 117
813 778 308 569 0 987 583
839 9 454 534 742 0 310
601 497 739 265 109 509 0
1 2 3 4 6 7

15 9 5 326
0 447 518 412 900 403 153 561 3 2 299 268 110 807 112
683 0 71 153 434 940 949 886 180 38 832 115 243 942 531
107 620 0 581 905 489 992 156 891 497 716 894 498 366 513
607 524 624 0 641 595 128 74 534 76 960 714 114 143 180
708 436 62 815 0 407 642 71 896 986 227 786 834 942 31
331 660 543 937 183 0 518 929 777 645 3 663 73 314 728
538 808 259 245 595 320 0 59 1 313 482 896 650 708 34
483 1 416 813 660 959 101 0 843 828 30 971 825 384 633
897 49 712 434 856 970 30 450 0 289 89 802 954 922 50
603 629 435 86 629 850 898 641 160 0 351 835 988 380 805
164 763 790 412 163 853 845 18 823 874 0 819 463 314 620
416 235 21 19 215 455 456 196 305 353 836 0 464 703 22
803 434 826 966 548 967 729 710 820 925 79 994 0 151 897
456 816 869 224 403 889 594 617 696 49 812 1000 753 0 999
815 808 372 970 241 198 287 141 516 16 850 335 940 929 0
2 4 8 9 11

10 10 6 960
0 88 332 808 438 498 615 810 467 208
359 0 754 348 226 769 549 561 60 477
240 150 0 6 727 407 402 437 714 687
444 989 19 0 147 428 702 307 218 200
921 379 18 480 0 89 771 179 314 891
728 226 303 556 818 0 804 561 544 210
963 333 275 1 776 263 0 372 275 43
73 581 612 624 853 342 642 0 685 430
764 863 95 7 942 321 309 498 0 138
112 410 33 321 372 365 595 373 493 0
2 3 6 7 8 9

20 4 10 928
0 2 976 645 373 693 591 97 185 152 192 303 754 712 353 320 855 607 226 639
546 0 914 186 347 48 92 441 150 305 33 93 982 386 68 978 110 112 569 559
296 72 0 750 950 177 813 654 848 667 261 426 305 806 339 843 152 386 286 944
887 590 328 0 331 571 713 750 549 823 862 469 381 509 540 482 459 68 295 112
916 961 372 341 0 618 177 31 460 680 416 97 624 654 686 303 336 609 16 85
509 190 946 329 570 0 455 220 403 265 287 49 728 202 362 100 894 979 628 924
790 660 339 886 635 344 0 923 937 679 883 952 116 743 141 413 71 62 867 642
817 483 929 865 211 482 226 0 662 376 556 289 651 345 300 342 582 934 685 505
223 716 739 526 831 482 667 243 0 904 80 462 546 248 944 826 113 506 659 690
167 386 246 808 37 590 107 378 172 0 393 62 28 615 129 766 140 959 247 158
554 151 590 15 696 837 310 873 301 168 0 531 991 334 917 236 493 953 177 600
330 700 992 743 727 958 872 493 97 182 91 0 607 735 241 196 101 288 32 763
512 333 282 43 675 615 959 910 108 263 86 59 0 592 786 402 686 864 359 557
356 807 91 799 765 177 391 960 630 679 344 744 190 0 28 25 584 702 991 542
963 450 156 400 508 747 537 261 785 401 971 693 108 130 0 783 906 894 312 297
854 941 327 549 684 868 576 708 452 629 50 345 591 500 501 0 990 359 599 879
620 383 279 590 428 738 71 210 644 965 521 292 170 461 970 718 0 496 189 645
555 640 273 605 337 215 104 189 556 462 139 434 433 874 712 23 301 0 450 93
862 445 409 383 88 578 195 57 295 43 245 291 597 237 563 553 925 777 0 656
465 333 470 603 118 902 476 830 276 128 631 721 990 427 129 724 514 59 918 0
3 5 6 11 12 13 15 18 19 20

11 5 7 472
0 290 449 840 191 276 21 819 756 651 891
745 0 429 371 468 294 429 737 215 486 49
85 481 0 309 542 390 121 924 428 589 769
150 878 217 0 342 421 845 362 591 600 365
481 696 793 203 0 515 87 632 251 653 469
651 89 949 959 631 0 690 80 554 470 20
322 971 250 891 312 670 0 87 674 612 686
38 444 733 830 646 247 268 0 629 497 273
97 148 361 397 458 991 87 537 0 544 556
909 218 878 158 108 190 179 194 863 0 790
231 252 233 963 433 230 209 701 211 57 0
1 2 3 5 6 8 11

15 12 9 857
0 88 329 286 670 932 870 632 365 452 192 417 662 249 741
968 0 804 425 23 169 100 516 423 671 564 232 810 842 551
705 308 0 399 144 989 685 814 920 906 797 636 357 989 404
18 237 144 0 338 392 569 360 913 20 228 335 42 143 918
852 984 820 908 0 644 219 51 632 903 216 903 160 13 891
517 353 294 534 941 0 790 871 332 358 583 244 729 162 578
771 304 848 974 640 667 0 881 283 885 283 266 139 499 520
299 863 762 815 215 56 700 0 155 845 923 838 554 857 434
634 18 363 756 321 210 729 312 0 877 609 946 761 244 211
252 742 83 550 956 844 716 170 251 0 415 676 447 689 865
1000 545 298 986 562 661 741 235 870 470 0 898 98 430 844
211 673 54 462 766 488 11 721 332 726 242 0 582 492 269
29 181 134 380 725 431 365 639 443 458 225 313 0 279 122
410 60 965 620 733 371 433 850 858 443 923 189 520 0 164
123 364 433 151 896 918 530 972 348 247 610 791 704 834 0
1 3 4 5 6 7 10 11 12

9 1 6 557
0 415 249 40 286 764 162 649 196
664 0 544 465 546 868 813 792 477
955 847 0 663 409 180 970 624 572
593 163 49 0 235 783 727 86 197
975 477 834 738 0 639 483 286 654
378 750 199 245 914 0 342 74 868
188 88 628 719 57 604 0 643 649
766 691 235 548 417 672 96 0 743
149 930 832 139 764 469 792 493 0
1 2 4 5 7 8

3 2 3 420
0 704 872
602 0 331
942 658 0
1 2 3

12 12 9 257
0 91 788 698 935 358 40 24 842 723 538 545
946 0 139 227 888 148 513 823 806 564 449 402
514 842 0 317 912 978 85 239 297 638 681 436
687 616 794 0 726 639 635 449 529 531 746 667
109 633 815 621 0 456 972 536 904 725 402 97
41 313 426 477 904 0 74 467 936 510 153 551
303 879 542 289 679 70 0 819 424 88 279 409
254 252 864 225 787 119 949 0 540 567 342 205
993 170 108 66 636 43 575 789 0 946 229 19
839 517 697 908 687 472 347 966 880 0 601 217
95 177 355 213 478 895 780 171 99 124 0 340
558 189 976 600 116 116 897 344 134 735 861 0
1 2 3 6 7 9 10 11 12

6 6 1 416
0 627 469 435 192 946
329 0 971 468 427 446
808 984 0 634 135 935
749 250 832 0 93 383
918 953 564 912 0 851
216 604 363 100 896 0
4

21 4 12 669
0 967 17 888 570 731 987 817 525 65 533 752 334 194 660 925 674 345 609 314 14
279 0 87 969 49 462 107 911 218 514 77 890 833 93 777 402 824 115 571 348 532
103 451 0 865 296 462 790 321 807 750 986 172 380 73 492 780 886 950 690 103 463
118 992 295 0 563 120 49 738 587 619 437 118 73 887 334 720 701 123 40 507 225
378 30 604 802 0 521 384 687 822 425 789 284 895 133 931 457 252 331 194 190 301
630 659 373 868 993 0 92 568 467 483 426 691 860 455 647 661 327 382 347 148 806
488 784 700 620 714 508 0 223 44 53 413 696 682 423 68 902 415 159 821 882 641
247 924 853 53 922 513 380 0 303 212 527 461 51 662 160 670 375 20 244 770 72
8 465 106 431 884 7 197 42 0 827 430 35 73 354 887 478 275 751 857 930 314
735 390 364 397 901 385 123 920 981 0 893 992 988 709 97 770 945 455 967 338 281
396 372 706 101 610 183 728 713 391 657 0 378 125 46 742 521 946 478 644 218 458
888 209 446 948 657 215 892 111 533 230 743 0 929 953 800 29 915 982 756 979 372
764 356 849 809 449 369 107 927 364 324 384 603 0 884 181 903 892 748 794 354 280
375 96 208 680 896 589 946 229 696 276 953 812 631 0 801 620 80 521 78 6 885
753 741 839 988 922 741 879 669 887 232 948 613 680 508 0 644 927 448 941 155 143
216 107 954 847 259 926 278 780 355 283 16 460 375 854 447 0 296 947 326 964 833
909 912 797 588 771 441 514 218 381 21 360 949 479 666 795 738 0 943 424 869 297
58 884 108 432 89 555 728 387 232 691 571 492 954 368 80 724 160 0 945 941 892
317 301 840 796 318 986 885 612 409 753 260 466 988 368 898 76 922 625 0 463 153
315 33 644 269 752 75 992 911 372 933 803 688 585 994 835 254 980 719 865 0 388
823 124 854 810 491 751 238 412 375 700 916 689 84 912 309 188 338 301 98 61 0
1 2 3 4 5 6 8 10 12 13 14 20

15 7 8 88
0 367 941 926 635 982 361 546 290 548 235 942 998 296 526
249 0 396 46 846 682 819 422 687 808 386 515 921 202 504
876 769 0 378 242 709 655 876 690 15 773 332 915 360 273
912 7 799 0 512 402 196 710 435 367 131 474 174 516 340
446 70 843 321 0 838 572 563 546 226 790 588 592 915 919
506 274 191 417 280 0 341 281 33 889 990 819 255 472 292
780 340 631 226 409 473 0 898 246 396 812 143 973 954 730
565 868 1000 70 141 543 839 0 772 235 471 156 123 460 974
377 283 266 157 622 896 734 30 0 721 983 275 116 795 418
89 748 499 5 615 851 426 107 393 0 616 230 627 86 385
102 897 358 478 180 623 986 801 871 71 0 183 591 54 809
58 848 226 498 947 77 502 913 279 280 19 0 23 895 248
1 981 984 102 229 341 580 408 964 917 561 186 0 988 95
128 393 903 185 592 481 35 538 557 888 450 187 167 0 820
209 62 67 209 394 402 311 622 742 242 382 57 158 294 0
3 5 7 8 9 10 13 14

4 1 2 843
0 832 770 940
369 0 678 179
818 864 0 698
637 72 111 0
1 4

10 3 6 374
0 542 890 568 782 180 473 614 301 764
334 0 979 295 152 842 992 140 266 102
547 898 0 957 354 192 433 903 727 643
509 771 145 0 708 664 35 275 446 566
100 411 866 215 0 744 196 861 247 390
852 739 655 305 637 0 904 261 990 95
694 893 821 688 753 943 0 832 812 607
218 438 404 783 537 814 1 0 104 909
548 964 508 937 168 598 591 472 0 234
846 733 223 940 778 467 112 465 571 0
1 2 5 6 7 8

9 7 7 326
0 489 900 127 348 836 646 945 427
117 0 530 624 201 753 564 978 571
675 794 0 142 81 442 875 741 307
694 156 306 0 402 384 658 564 225
557 42 572 392 0 687 869 170 156
398 794 356 502 709 0 686 425 735
479 566 816 920 440 556 0 578 486
712 884 239 447 541 802 23 0 449
196 595 192 234 815 362 741 212 0
1 3 4 5 6 7 9

11 1 8 999
0 683 735 48 921 181 940 75 204 388 622
150 0 580 855 316 293 948 527 799 396 944
365 881 0 785 665 844 191 781 431 389 452
596 71 186 0 643 344 718 583 418 273 322
39 774 901 245 0 89 545 192 968 695 587
911 411 819 696 76 0 15 238 856 445 626
659 40 49 196 35 392 0 265 969 161 538
290 551 311 543 147 400 87 0 339 719 134
277 629 544 96 676 971 110 914 0 178 906
539 836 298 939 383 684 682 648 652 0 194
185 941 744 847 835 891 598 274 581 316 0
1 3 4 6 8 9 10 11

20 17 11 624
0 37 402 133 927 999 406 859 667 164 67 963 465 371 934 89 487 171 891 509
298 0 528 180 715 547 534 462 566 539 755 120 837 791 521 969 69 872 726 927
538 241 0 993 852 57 715 137 146 554 659 36 62 956 915 242 671 813 127 484
730 666 590 0 850 502 732 722 822 152 945 899 430 834 139 775 685 547 489 174
44 394 832 79 0 456 140 345 49 162 158 175 645 887 192 587 88 693 318 810
866 470 754 764 251 0 940 254 25 624 801 866 797 844 259 981 275 714 120 619
114 281 776 641 277 15 0 832 863 102 877 533 911 742 354 17 858 604 956 111
629 931 263 494 80 107 752 0 60 733 818 531 703 283 811 831 923 87 845 107
302 946 983 834 209 76 539 577 0 933 142 884 396 122 166 658 967 245 116 71
656 848 888 186 551 522 348 733 445 0 435 577 903 88 874 885 921 82 960 811
10 245 952 893 640 426 411 649 392 7 0 765 462 663 964 701 200 866 223 548
598 19 334 174 273 421 48 157 693 481 468 0 503 843 64 806 87 703 231 497
352 975 504 468 788 518 431 841 717 297 415 616 0 894 433 301 420 57 73 819
565 765 651 32 619 493 448 777 580 502 359 428 205 0 333 931 672 473 448 455
313 517 751 727 132 996 511 785 767 567 857 937 131 974 0 588 514 944 432 961
720 363 463 79 791 667 763 721 691 235 521 145 899 37 247 0 625 520 594 135
656 361 701 513 649 183 838 236 697 781 20 657 501 382 471 931 0 172 490 45
245 180 632 117 676 530 505 274 507 376 867 641 32 579 694 544 228 0 876 381
815 924 513 834 933 13 568 755 295 91 244 340 335 775 971 803 802 852 0 307
75 358 683 942 351 714 520 44 609 99 271 341 914 547 853 99 479 218 666 0
2 3 4 8 10 11 12 13 14 16 18

7 6 1 47
0 729 552 831 86 586 772
788 0 651 644 183 611 742
806 303 0 7 352 508 106
182 77 771 0 766 940 527
594 143 970 549 0 19 567
305 747 470 135 185 0 56
259 972 58 254 155 669 0
7

8 8 4 50
0 846 460 555 340 781 455 358
347 0 111 457 168 597 993 223
855 316 0 633 108 822 301 455
133 975 160 0 795 805 970 990
62 550 951 907 0 361 857 598
141 311 308 839 421 0 116 7
369 108 581 224 423 213 0 683
245 865 489 377 840 648 524 0
2 4 6 7

10 7 2 426
0 210 105 687 568 474 794 501 49 569
65 0 731 813 930 220 541 121 219 416
468 836 0 929 876 354 95 191 232 766
456 603 98 0 379 165 555 66 84 28
211 584 76 779 0 649 158 943 930 729
836 402 948 251 869 0 135 531 744 488
626 287 71 391 94 26 0 840 824 190
746 889 273 773 452 857 200 0 230 857
358 525 786 438 360 187 385 610 0 407
519 141 502 358 118 788 781 860 233 0
5 9

16 11 5 805
0 652 174 412 522 666 914 232 783 53 12 642 638 817 693 46
515 0 841 694 133 409 442 312 881 123 346 710 328 166 977 892
523 980 0 417 287 853 435 552 84 217 956 447 211 593 615 255
990 129 95 0 684 614 855 477 925 736 599 622 445 926 139 773
169 662 752 585 0 300 605 19 851 40 588 806 487 798 751 453
404 740 582 850 423 0 195 704 899 471 791 849 92 236 126 231
8 294 244 112 879 543 0 68 249 393 107 836 550 945 985 300
398 740 40 331 589 814 877 0 293 65 347 83 913 790 670 391
372 30 684 615 493 914 509 560 0 515 901 666 350 803 963 687
102 712 426 141 42 15 307 918 659 0 371 616 93 635 405 115
25 777 144 61 743 636 326 252 547 840 0 504 212 542 306 526
228 408 237 5 900 630 371 558 899 29 928 0 514 474 915 271
588 939 47 83 351 141 70 677 392 616 868 248 0 179 409 553
705 988 312 293 993 564 923 715 121 821 96 401 335 0 569 315
605 508 605 3 590 956 495 659 984 887 626 851 486 804 0 612
38 508 599 702 801 943 617 75 658 89 895 753 489 581 673 0
7 10 12 13 14

14 7 7 341
0 67 166 199 219 108 167 293 117 256 539 221 744 120
893 0 899 656 72 10 547 544 428 932 674 829 555 429
432 15 0 988 647 512 406 812 63 976 271 229 620 388
484 158 960 0 580 629 853 830 637 276 839 535 820 266
818 493 94 724 0 274 525 738 261 523 249 18 686 663
993 957 892 612 696 0 375 121 655 306 750 859 135 738
135 973 272 306 590 89 0 150 35 812 423 560 549 35
434 149 52 120 812 396 428 0 55 359 123 781 480 129
87 581 988 221 318 474 546 589 0 131 135 677 280 170
840 55 81 740 89 514 240 493 985 0 51 888 412 457
247 886 238 78 15 324 658 354 544 975 0 179 89 915
661 224 943 940 745 134 346 825 873 435 690 0 112 279
675 515 518 86 971 764 324 208 193 690 531 850 0 43
427 176 573 867 442 233 90 384 524 186 517 870 362 0
1 2 6 8 9 10 11

19 3 5 450
0 930 77 865 665 601 403 534 822 764 274 829 815 478 762 892 196 564 407
237 0 482 244 485 593 123 967 905 43 876 392 536 299 673 964 515 690 916
917 223 0 737 681 496 565 847 326 678 91 521 594 497 109 427 92 593 19
214 912 923 0 257 787 667 144 437 691 107 951 380 375 220 602 111 252 450
28 98 775 705 0 540 647 650 36 756 77 480 700 95 45 611 370 653 397
388 796 833 78 255 0 136 458 629 707 411 91 958 860 118 407 634 175 947
633 824 334 388 252 813 0 87 699 210 50 68 862 446 807 10 631 884 616
118 693 244 824 104 686 781 0 315 156 187 301 330 485 933 505 819 320 109
983 758 807 192 807 226 54 605 0 32 415 235 267 30 704 960 625 527 415
310 659 729 465 197 381 146 682 313 0 651 500 984 759 482 742 917 26 548
142 79 504 173 493 738 791 522 793 102 0 498 319 516 807 329 597 272 526
977 769 559 642 771 58 625 881 891 366 797 0 916 266 938 346 769 462 190
859 253 63 651 706 560 322 574 367 2 170 990 0 527 498 758 85 139 529
494 116 409 737 481 558 652 98 495 350 867 309 539 0 77 913 602 79 618
161 752 191 879 754 712 868 280 562 978 717 700 858 562 0 815 618 298 648
175 302 97 670 651 315 330 189 391 242 142 470 859 303 221 0 402 181 974
113 401 606 674 378 674 726 235 235 892 204 885 891 379 186 988 0 400 188
302 729 728 45 970 870 866 180 172 438 581 704 764 46 104 721 71 0 833
394 148 419 980 392 623 216 282 1 753 621 400 940 275 480 668 319 449 0
1 3 4 10 18

0 0 0 0
AC output:

Code: Select all

640095
598805
625140
58464
807107
872715
681600
851966
464701
742143
728489
554389
43625
663432
333344
53249
267294
600946
260528
718336
558598
697991
185618
859636
475889
254124
239749
855764
314259
831793
901371
416729
836950
494888
380600
242704
406338
655966
85932
669488
363567
303172
946839
602504
40015
45650
392101
783388
335142
437499
Check input and AC output for thousands of problems on uDebug!

wurr
New poster
Posts: 2
Joined: Sun Jul 06, 2014 7:17 pm

Re: 10702 - Travelling Salesman

Post by wurr » Sun Jul 06, 2014 7:31 pm

Don't understand why I'm getting WA on this. Anyone can spot anything? Seems to pass all of brianfry's test cases :/

Code: Select all

#include <cstdio>

using namespace std;

int main() {
	while(1) {
		int c,s,e,t;
		scanf("%i%i%i%i", &c,&s,&e,&t);
		if(c+s+e+t == 0) break;
		int profit[c][c];
		for(int i=0; i<c; i++)
			for(int j=0; j<c; j++)
				scanf("%i", &profit[i][j]);
		int end_cities=0;
		for(int i=0, j; i<e; i++) {
			scanf("%i", &j);
			end_cities = end_cities | 1<<(j-1);
		}
		int dp[t+1][c],i,j,k; // dp format = number of remaining travels, from node
		for(i=0; i<c; i++) {
			if((1 << i & end_cities) != 0)
				dp[0][i] = 0;
			else dp[0][i] = -1; // -1 = not arriving at end city
		}
		for(i=1; i<=t; i++) {
			for(j=0; j<c; j++) { // calc max profit from node j with t remaining
				int max=-1;
				for(k=0; k<c; k++) {
					int p = dp[i-1][k];
					if(p == -1) continue; // does not arrive at end city
					p += profit[j][k];
					if(p>max) max = p;
				}
				dp[i][j] = max;
			}
		}

		printf("%i\n",dp[t][s-1]);
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10702 - Travelling Salesman

Post by brianfry713 » Tue Jul 08, 2014 1:35 am

Input:

Code: Select all

51 48 26 837
0 37 883 649 374 469 552 780 612 480 852 501 105 391 584 39 440 593 223 406 140 425 947 511 619 896 565 152 906 913 883 625 301 117 273 674 585 824 806 196 656 9 49 760 399 984 799 190 577 373 595
716 0 149 894 227 119 789 143 622 46 407 857 670 707 973 943 733 910 118 890 457 773 898 505 533 649 489 683 838 417 407 785 132 555 678 710 25 466 853 647 512 259 503 533 318 827 475 50 736 593 291
545 717 0 188 401 249 836 241 283 26 657 689 810 141 595 487 850 620 304 702 618 815 313 120 700 630 298 174 31 386 118 673 930 835 860 330 435 48 571 718 425 579 406 234 719 1 720 569 972 23 622
589 190 934 0 60 889 915 357 414 945 742 884 617 671 70 829 353 504 228 275 221 652 853 979 237 924 331 956 492 302 330 465 242 519 399 301 759 313 657 173 610 399 408 578 421 477 758 125 980 337 399
553 340 604 883 0 576 527 213 531 370 866 213 834 107 731 584 759 842 249 415 366 858 165 773 787 938 249 897 62 228 233 813 132 573 416 14 148 294 226 31 15 443 243 848 901 325 432 659 166 680 426
531 889 590 655 27 0 879 903 923 941 483 508 753 614 80 520 628 579 813 205 961 827 648 203 26 548 880 809 559 45 840 984 928 80 925 934 107 804 837 29 96 319 536 200 932 967 719 911 546 883 116
858 61 115 61 438 14 0 940 247 572 336 438 555 615 518 480 549 624 635 385 4 730 55 892 929 338 858 999 249 755 233 364 613 293 478 25 82 843 964 680 415 651 118 969 266 635 800 166 610 434 902
613 163 956 504 443 293 714 0 441 541 468 673 256 432 317 85 456 399 928 771 78 342 422 195 662 39 181 814 204 790 247 457 755 762 412 258 204 56 971 997 949 791 669 204 222 338 641 678 736 920 800
165 613 221 712 274 611 892 87 0 166 34 686 622 788 447 33 397 2 89 368 998 389 510 19 592 731 356 584 760 443 503 560 607 115 132 318 741 743 562 827 260 595 864 882 734 662 914 130 664 354 849
13 742 358 31 686 441 738 621 552 0 180 124 463 787 590 947 456 330 689 17 509 300 611 372 181 696 34 447 826 49 800 26 61 894 384 444 931 176 181 903 727 361 378 190 499 968 488 954 649 528 971
157 827 933 881 8 629 266 454 806 314 0 605 831 726 850 566 169 780 741 702 35 820 62 412 361 560 379 848 865 28 375 835 536 201 120 768 208 100 33 661 905 698 266 735 776 115 301 296 247 393 997
281 212 410 44 572 321 423 771 186 802 145 0 372 689 346 491 457 905 590 841 566 494 891 183 581 666 649 233 961 247 977 310 879 189 719 923 112 40 697 883 225 498 27 948 538 724 439 994 629 380 187
546 226 77 728 806 94 728 390 406 975 366 715 0 853 906 786 127 370 825 823 252 401 320 630 348 210 706 138 203 334 518 741 231 743 169 310 900 262 37 641 20 363 358 734 568 264 519 694 633 695 517
236 447 188 217 795 397 274 284 952 959 153 692 189 0 895 861 498 146 474 887 786 493 249 496 579 816 759 449 510 743 496 378 330 942 565 546 88 962 820 372 265 778 524 956 319 771 168 816 916 994 702
54 838 303 549 768 118 659 217 979 401 712 708 730 5 0 273 627 93 586 798 464 850 928 987 157 246 757 677 61 25 22 115 430 859 417 330 627 886 988 195 217 740 258 924 821 262 548 799 354 485 597
169 686 876 508 195 121 264 223 533 640 244 647 421 454 415 0 750 80 653 89 626 869 180 235 144 352 849 44 503 202 528 451 723 214 326 230 760 446 845 982 978 485 225 977 257 678 743 359 110 395 447
87 615 979 322 111 682 170 154 184 723 681 634 445 246 959 26 0 5 404 871 338 734 707 562 62 963 592 804 321 701 199 120 139 165 98 460 275 779 981 428 315 704 461 948 500 58 907 526 415 662 396
752 747 454 666 808 416 257 964 737 309 514 208 447 678 657 907 305 0 787 887 84 101 942 544 49 794 954 307 671 368 320 418 471 419 871 136 578 286 744 541 374 52 54 581 499 84 237 405 388 24 643
471 124 937 367 524 82 672 830 752 391 502 169 861 920 39 349 497 324 0 92 390 50 144 443 630 642 878 867 398 617 242 392 440 365 680 806 241 761 477 70 512 219 923 32 79 194 70 427 691 746 871
432 795 14 226 424 7 104 642 404 720 883 147 159 600 827 316 840 939 144 0 261 451 362 184 834 441 729 904 219 419 1 89 202 795 454 428 570 460 531 212 215 602 446 362 761 397 540 428 236 478 572
497 280 285 32 114 77 760 369 296 531 369 736 732 163 190 511 84 1 41 295 0 216 643 93 577 755 489 116 534 725 945 105 573 225 742 956 338 818 67 706 465 949 74 201 33 588 742 543 671 94 936
318 309 930 762 237 36 250 704 569 326 649 26 250 225 767 557 562 584 624 619 49 0 924 44 601 956 983 694 851 653 787 786 322 448 67 83 36 102 333 740 670 10 740 695 260 964 461 816 877 397 791
847 797 67 890 397 22 872 442 224 876 580 361 198 27 427 632 415 528 964 506 550 326 0 245 244 937 560 57 104 436 805 895 634 601 961 523 997 334 746 790 910 621 369 270 170 748 697 802 162 576 117
667 125 442 263 721 378 822 777 834 609 581 80 242 181 392 116 529 725 861 318 986 833 38 0 256 3 785 952 804 298 879 272 316 4 714 578 724 443 751 852 276 359 432 355 952 964 746 419 844 823 279
513 808 464 550 415 466 687 718 621 984 597 892 652 600 957 229 675 752 980 526 27 690 309 734 0 994 272 831 412 467 5 43 979 165 506 528 579 323 566 297 943 902 893 186 553 844 143 781 518 894 112
43 272 802 703 357 147 326 540 558 792 544 600 770 60 457 649 639 779 215 935 721 116 179 907 668 0 22 401 800 891 646 912 285 269 65 987 978 211 312 517 120 103 412 720 224 472 176 872 110 955 438
396 27 553 926 285 572 299 37 372 189 682 635 825 303 699 811 280 261 474 796 380 928 559 451 151 30 0 627 374 491 933 812 886 311 716 163 596 288 461 632 11 1 666 645 825 320 695 987 599 307 460
746 686 739 304 489 241 686 467 615 176 399 426 414 61 141 576 656 780 37 640 790 389 657 786 214 976 832 0 552 926 490 12 671 528 102 326 16 343 11 482 309 539 232 734 952 292 226 527 300 358 915
291 499 656 947 637 869 274 820 420 199 310 783 221 837 237 898 204 579 909 685 887 799 268 972 750 911 549 628 0 210 906 895 852 405 550 798 393 770 423 212 541 621 521 324 193 709 560 91 912 490 351
948 728 149 215 699 898 478 599 877 39 505 771 891 261 672 40 653 441 463 864 982 83 737 657 276 445 216 718 357 0 57 68 656 784 216 223 834 465 700 432 341 738 288 464 980 900 135 20 904 576 482
120 557 916 856 565 191 652 780 260 360 188 327 16 323 542 238 156 358 289 587 699 378 227 162 358 126 648 377 30 223 0 210 501 131 125 356 695 668 7 826 927 367 365 254 734 687 147 323 842 505 611
781 555 340 359 68 697 484 715 425 865 290 986 365 772 111 72 819 130 431 996 56 797 361 661 882 47 160 204 241 664 166 0 373 570 505 731 637 202 566 351 978 431 992 964 147 764 426 571 582 555 1
577 962 149 289 623 30 336 134 585 928 797 750 300 366 254 30 354 807 595 704 785 377 48 100 876 811 525 446 392 79 446 320 0 392 946 609 366 975 296 499 559 223 295 660 874 12 913 255 717 72 201
421 208 930 468 307 805 630 183 602 373 613 399 692 4 344 652 370 670 947 868 228 521 515 239 746 878 151 1000 595 222 201 367 429 0 130 186 87 286 815 269 887 187 881 285 230 885 980 882 606 649 180
473 228 53 987 466 798 865 968 150 459 190 350 825 970 831 10 57 116 176 677 354 362 558 990 943 794 969 176 751 969 708 223 196 760 0 562 661 909 778 628 58 588 169 759 764 491 941 125 899 56 300
575 761 13 484 750 955 629 70 131 379 38 190 954 233 949 515 245 209 644 225 619 231 393 377 994 235 670 118 133 77 769 708 838 781 543 0 587 87 172 9 569 550 46 758 855 279 706 369 875 267 12
99 885 594 844 613 587 78 282 56 211 359 824 270 196 604 812 134 691 335 142 259 237 540 17 91 170 74 460 44 340 823 495 576 417 338 189 0 355 767 470 411 329 180 234 950 727 190 762 213 232 448
706 490 684 245 858 775 414 284 586 810 623 408 304 199 176 641 739 531 759 560 293 88 740 878 37 466 67 150 30 298 598 736 140 281 332 349 407 0 746 632 992 555 607 400 210 805 927 850 543 809 960
454 101 399 193 979 788 11 45 937 40 695 886 127 186 519 459 534 925 556 166 917 110 772 668 319 928 946 520 822 755 831 275 855 230 820 833 17 830 0 230 305 221 276 191 348 461 709 158 346 985 713
863 253 174 986 272 492 913 218 363 86 972 193 713 826 774 532 11 790 713 592 95 933 867 637 632 679 697 789 376 33 853 239 286 26 224 557 869 489 774 0 231 574 97 776 638 923 901 169 285 691 233
228 137 166 446 125 149 124 173 290 499 205 142 89 490 168 313 399 36 801 172 619 726 269 746 364 543 646 884 179 688 117 406 176 634 851 300 782 326 472 423 0 176 677 565 265 518 84 929 916 119 81
440 737 806 60 482 521 602 480 757 132 167 873 537 343 858 739 994 639 64 466 414 591 494 978 207 11 61 135 927 531 215 366 620 373 425 453 245 378 932 1 861 0 99 225 749 441 82 487 786 73 902
251 486 844 96 463 51 107 875 185 385 757 752 102 376 124 878 829 720 607 760 721 467 210 945 215 2 27 53 788 99 306 38 584 149 486 398 199 592 624 384 328 380 0 487 781 756 610 658 936 329 616
695 401 82 905 698 648 906 724 52 693 174 357 83 109 505 568 858 704 511 481 439 190 212 925 970 319 886 979 254 566 594 301 967 27 205 664 26 462 739 77 507 912 433 0 941 372 937 508 229 992 370
61 430 559 272 706 528 943 591 506 196 157 451 496 475 477 52 490 502 514 228 578 372 491 362 312 862 650 171 442 642 540 502 423 450 125 481 977 67 71 834 263 579 284 110 0 405 112 162 894 613 27
473 542 398 963 903 709 176 904 879 617 897 770 470 320 219 947 152 547 13 222 732 627 153 367 737 909 478 250 803 442 276 275 983 673 590 237 733 117 492 963 734 389 732 555 708 0 950 501 859 848 514
432 579 492 936 945 580 845 774 829 999 215 104 625 549 128 566 137 212 683 628 174 416 16 905 322 75 206 823 285 405 688 69 983 179 356 279 111 200 52 939 550 266 395 175 166 522 0 740 302 734 422
282 259 189 297 164 863 724 721 685 8 126 724 428 460 254 784 739 364 335 790 303 885 408 697 59 573 570 150 227 655 924 860 914 464 508 429 326 231 501 362 591 626 437 18 86 691 801 0 824 406 136
965 708 372 372 756 782 297 678 931 875 684 206 734 597 670 241 377 347 824 878 61 766 855 497 783 292 187 936 467 593 423 432 652 794 155 760 575 803 789 857 677 472 415 762 421 436 355 149 0 782 178
26 842 943 881 691 77 172 229 364 639 821 786 422 825 931 576 936 857 379 724 66 407 547 480 169 967 915 523 116 48 52 493 242 346 725 932 774 249 160 138 239 333 275 660 509 558 587 444 766 0 317
519 831 724 417 662 244 736 928 118 851 328 169 695 569 866 420 852 991 20 363 128 258 47 755 269 555 664 855 350 429 524 220 612 247 637 273 490 372 553 607 574 880 127 620 800 344 391 3 334 410 0
4 5 8 9 12 15 16 19 20 21 24 25 29 32 33 35 37 38 39 41 43 44 46 49 50 51

0 0 0 0
AC output: 829869
Check input and AC output for thousands of problems on uDebug!

wurr
New poster
Posts: 2
Joined: Sun Jul 06, 2014 7:17 pm

Re: 10702 - Travelling Salesman

Post by wurr » Tue Jul 08, 2014 9:49 am

Thanks a ton brianfry, got my AC now :)
For anyone wondering what the problem was, end_cities, being an int, couldn't hold all possible city identifiers (up to 100).

Post Reply

Return to “Volume 107 (10700-10799)”