forked from guillaumeportails/Christofides_Algorithm_Cpp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
tsp_example_3.txt
15112 lines (15112 loc) · 241 KB
/
tsp_example_3.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
0 13139 9322
1 5826 1350
2 413 10751
3 8419 4442
4 4317 8968
5 7196 20891
6 9440 14145
7 10744 13211
8 10215 5722
9 12079 4397
10 2279 7154
11 14035 12069
12 10052 5416
13 6807 5198
14 11615 11533
15 9730 12076
16 8245 4619
17 5738 6660
18 9010 7394
19 3437 7417
20 7689 712
21 4225 3856
22 9418 14571
23 6387 17544
24 14326 4951
25 8098 2651
26 2351 9390
27 2281 7086
28 8184 21654
29 6523 23145
30 11052 15120
31 12745 18967
32 7398 4252
33 7762 13084
34 8331 16172
35 8242 4799
36 10780 4473
37 10068 7229
38 6963 6247
39 10589 2392
40 9729 3166
41 10629 2958
42 2045 9456
43 3408 7154
44 9095 15592
45 9074 18430
46 8114 14387
47 10171 14500
48 12940 3586
49 11904 21053
50 12775 9211
51 14017 10557
52 6931 20563
53 6797 14518
54 13784 10255
55 6841 4757
56 10306 3301
57 6048 16797
58 433 8332
59 12389 11185
60 7348 19276
61 7180 20712
62 6123 6097
63 13393 3528
64 2401 14736
65 6924 17692
66 16090 19856
67 16042 20711
68 7380 16763
69 7670 21933
70 4097 13712
71 12179 11258
72 7194 18798
73 11118 13021
74 9599 9802
75 10172 16594
76 7095 12403
77 7774 22885
78 8770 16294
79 6489 15202
80 13367 4841
81 14296 4201
82 7285 6542
83 10130 8906
84 11119 7623
85 2163 9776
86 9298 20712
87 8668 19651
88 16149 15177
89 14436 15509
90 15136 16369
91 13052 21452
92 6524 22392
93 12706 21923
94 6808 22324
95 6961 22313
96 15124 4032
97 10609 3276
98 7342 3852
99 9382 2518
100 4947 2696
101 8404 1508
102 6631 3859
103 6925 4207
104 14686 3690
105 9126 8625
106 5915 3960
107 11801 4032
108 4116 10073
109 10212 3462
110 14454 1288
111 9206 3435
112 13659 4550
113 3722 1287
114 8420 1659
115 9356 1269
116 13952 11559
117 12221 13981
118 10058 11231
119 4271 590
120 13574 9942
121 6936 21125
122 11703 10993
123 7344 3975
124 11562 12175
125 8556 7377
126 2722 6729
127 4401 7481
128 4329 7094
129 9506 10073
130 13285 12288
131 9533 19665
132 6205 2495
133 840 11117
134 14676 3756
135 5553 2152
136 9509 4479
137 10036 5104
138 9080 2438
139 2411 8417
140 7662 4470
141 11422 6323
142 7908 14342
143 4283 16024
144 2240 8798
145 6469 19224
146 2274 10511
147 11004 16298
148 8174 15178
149 7598 11336
150 3099 8971
151 10298 10805
152 5522 22885
153 2457 7494
154 4220 9040
155 10544 10194
156 5603 11372
157 5875 10278
158 3466 7814
159 6217 1002
160 10470 15077
161 10781 5761
162 11594 3196
163 12958 21287
164 7435 2146
165 10986 2262
166 9900 3766
167 7432 1951
168 7696 2856
169 9685 12018
170 7136 4726
171 10145 13401
172 10973 12544
173 6443 22486
174 3481 10269
175 10280 9303
176 8182 14472
177 1389 13253
178 3952 10165
179 10309 11557
180 4917 2941
181 3514 9663
182 5395 7338
183 4031 10632
184 997 7983
185 599 11082
186 3771 7336
187 6808 10485
188 4831 7440
189 11499 13492
190 7201 21847
191 13802 15051
192 11228 20707
193 7593 21785
194 16237 15569
195 12558 20582
196 12516 18069
197 16507 15856
198 16758 16099
199 10755 19902
200 9460 19488
201 14240 19212
202 13663 17470
203 15907 14968
204 13357 19436
205 12665 19172
206 15740 15480
207 13204 20141
208 16926 16335
209 10739 19071
210 16833 15998
211 10924 10800
212 10712 18541
213 14317 20292
214 6956 4111
215 16446 16767
216 17909 11730
217 10681 14631
218 16161 13501
219 4524 5944
220 6113 3790
221 12673 3582
222 11024 6191
223 14043 21794
224 12814 4744
225 3631 12268
226 2202 9875
227 9099 13763
228 13464 12450
229 3815 7518
230 6173 13657
231 15761 10703
232 11318 10762
233 3313 14613
234 11449 10041
235 10062 13548
236 7025 7560
237 13072 11285
238 9658 9906
239 4171 9353
240 12946 6280
241 10273 7524
242 10141 9909
243 11303 9884
244 3022 6825
245 9377 11778
246 14063 20019
247 11548 20772
248 13568 12259
249 10665 15220
250 8002 22018
251 15318 17425
252 12691 18691
253 8463 21907
254 2692 6476
255 14359 22780
256 3518 10342
257 9749 21116
258 10727 8569
259 13570 1858
260 9367 17941
261 7472 19906
262 9451 3321
263 13729 21861
264 6646 3700
265 10488 16816
266 6091 9045
267 10071 1279
268 12668 7289
269 8475 2354
270 5318 3696
271 13028 5340
272 14348 19817
273 11185 14407
274 12097 16750
275 3090 8316
276 10937 13419
277 9326 10322
278 9352 11579
279 7686 7248
280 14057 14546
281 12786 3259
282 16326 16601
283 14027 11632
284 16060 17235
285 10483 2551
286 8284 3654
287 7120 2294
288 5717 4137
289 2798 5714
290 7335 4711
291 15507 17612
292 12778 13486
293 13349 20439
294 12896 11100
295 15636 17748
296 15417 16331
297 2722 8193
298 4273 6638
299 14319 17771
300 5130 6000
301 12829 9797
302 11670 4675
303 10977 16574
304 14084 11243
305 13349 11324
306 13844 2566
307 10873 3049
308 16048 17012
309 16216 17016
310 1956 8107
311 5190 6396
312 939 8372
313 7293 1638
314 2762 8539
315 14251 18396
316 16378 16794
317 8699 1226
318 16232 20113
319 3276 8183
320 15425 19901
321 16334 16949
322 8070 19984
323 6363 8406
324 4382 7374
325 9662 2013
326 12056 6398
327 8626 17922
328 13119 1820
329 9259 4101
330 11363 13742
331 585 7971
332 676 8450
333 15512 10805
334 13447 12253
335 10855 10461
336 5982 3598
337 9132 12015
338 9953 6268
339 8510 19675
340 11856 6356
341 6075 10618
342 6627 7014
343 13330 2671
344 10796 14613
345 7945 3639
346 7724 930
347 10776 1698
348 8394 10230
349 10049 14330
350 6931 18672
351 3007 9579
352 3602 16094
353 10043 11507
354 10170 17088
355 5675 5732
356 5102 10676
357 9930 10470
358 14294 1258
359 15879 17781
360 11619 15508
361 11972 12743
362 3316 9783
363 13788 19125
364 15133 20386
365 4126 16160
366 14274 10052
367 14188 13684
368 15898 13203
369 10975 13013
370 4001 5671
371 4946 13056
372 9406 5897
373 2393 9179
374 14780 10260
375 11024 1056
376 13771 9787
377 6605 10651
378 1862 9549
379 12153 2309
380 6956 15287
381 4071 18265
382 10553 16648
383 7505 18877
384 10218 1503
385 9979 10963
386 9303 1877
387 11232 11357
388 7745 18737
389 6139 18945
390 7739 19577
391 4255 7941
392 9669 13077
393 4027 3567
394 2268 9130
395 9505 5414
396 1817 9581
397 15114 18714
398 11090 17178
399 1605 8146
400 16460 15968
401 12159 13558
402 8203 12444
403 15143 13525
404 10948 3501
405 2368 9433
406 8187 980
407 3532 7847
408 3357 8133
409 7437 13980
410 6911 21137
411 6538 22365
412 4270 7643
413 7950 20575
414 6507 19399
415 14443 5504
416 12076 16549
417 8091 22649
418 12823 9482
419 4409 12565
420 14033 5946
421 14439 11406
422 13676 11186
423 16191 11751
424 17777 12209
425 14490 10038
426 10851 10063
427 12395 10020
428 3942 9905
429 10108 10746
430 11143 13436
431 8143 8048
432 14121 3639
433 6312 12463
434 8026 20807
435 14420 5712
436 14000 11519
437 10789 12407
438 9143 18688
439 3678 9397
440 14386 13037
441 12686 8369
442 656 8602
443 2674 7644
444 3078 10286
445 9213 10406
446 9912 3976
447 8273 12149
448 13681 5029
449 6513 8064
450 9550 11465
451 13195 2481
452 13168 1157
453 3260 6971
454 3578 13799
455 8872 21126
456 7694 22022
457 8646 10000
458 11076 13658
459 11862 2375
460 6315 16812
461 8191 18443
462 6946 4927
463 9391 11104
464 10081 14176
465 6434 4740
466 4136 7901
467 7573 6284
468 8627 3494
469 3802 10394
470 10002 14199
471 4067 11720
472 3935 9103
473 12078 3871
474 11919 3429
475 7640 2287
476 17250 14490
477 13379 4658
478 3890 10377
479 11322 14170
480 3676 1739
481 4562 4866
482 11887 3591
483 8344 6683
484 9107 9189
485 13823 12921
486 2205 8851
487 12743 11863
488 13644 10044
489 3703 8759
490 3337 7695
491 7327 4782
492 14650 4436
493 14079 10359
494 11559 7157
495 13061 9802
496 14434 12037
497 11369 11575
498 14055 11048
499 6764 15136
500 12992 4620
501 10730 7783
502 3144 1249
503 10104 3000
504 5796 14128
505 5861 21878
506 14423 10782
507 6883 15646
508 9510 4998
509 7855 20941
510 10063 12600
511 7501 1680
512 12682 11638
513 4242 9368
514 11279 17522
515 12026 10366
516 8827 19167
517 8240 8648
518 7374 8677
519 9087 5715
520 9913 6845
521 3486 19079
522 7478 22974
523 10404 14673
524 13483 13213
525 7698 20418
526 1350 7985
527 861 9277
528 14908 4198
529 6115 23480
530 6746 20462
531 5916 18640
532 11997 1743
533 1167 7154
534 9851 3099
535 5173 9999
536 12471 1818
537 15067 21957
538 11732 13709
539 13106 12360
540 2291 9326
541 11302 3958
542 12103 13554
543 11864 16615
544 8777 2279
545 6139 8021
546 13034 2106
547 13072 18104
548 11505 20355
549 13023 5102
550 3695 8378
551 3556 10467
552 10226 9440
553 8869 3803
554 10940 11899
555 7056 4793
556 12485 4800
557 12483 1414
558 12315 8222
559 3091 1045
560 2733 15448
561 4083 5350
562 10777 10957
563 5057 11477
564 11611 8293
565 2208 8471
566 9336 17778
567 11362 11944
568 14704 3277
569 10743 10302
570 8412 8925
571 12901 8894
572 8018 20406
573 2826 9830
574 7816 9106
575 7444 2036
576 4748 9112
577 9843 8998
578 7634 3666
579 11747 21037
580 6354 13545
581 13297 13210
582 4458 6493
583 12291 12240
584 5127 1951
585 6480 15156
586 12744 9102
587 3644 9267
588 5205 10509
589 13102 1559
590 5021 15459
591 12487 1131
592 10410 12374
593 15958 17068
594 6589 5683
595 15200 3028
596 8262 13979
597 16114 10977
598 8716 13806
599 9343 14005
600 11344 1030
601 4988 4366
602 7662 10856
603 2857 9853
604 5445 8878
605 2724 10250
606 4443 14942
607 7178 13263
608 8374 8751
609 10967 19946
610 11927 11035
611 6193 7340
612 9186 9074
613 11613 11702
614 12222 11091
615 10471 802
616 3885 7722
617 3396 1646
618 5071 11060
619 4531 14774
620 9497 11582
621 11900 12510
622 13471 11803
623 9139 13215
624 8938 10693
625 14942 13046
626 5587 4286
627 5927 13724
628 4133 10195
629 7758 6480
630 7217 15019
631 3839 7614
632 1761 10009
633 17513 13297
634 5715 9317
635 7024 15465
636 2456 9962
637 8628 9138
638 5911 15079
639 8938 20063
640 6932 8844
641 4478 3233
642 6807 14332
643 6358 5736
644 14370 1029
645 4723 3237
646 4675 14779
647 16096 15539
648 9320 13128
649 4036 484
650 8249 14584
651 7266 10089
652 5795 14683
653 8713 10687
654 4649 13137
655 16526 11248
656 13579 13501
657 5436 5700
658 7545 1858
659 4363 8642
660 9545 20413
661 8785 20468
662 5125 8659
663 6957 9060
664 8179 12093
665 11536 9324
666 10422 13549
667 13178 21091
668 11439 11560
669 5512 4007
670 9888 11747
671 11548 1092
672 7835 3699
673 7003 3383
674 5706 8739
675 7744 1595
676 11891 946
677 6494 11671
678 11937 17413
679 6478 5716
680 9080 6524
681 9480 1844
682 8035 1551
683 4440 18136
684 4344 16424
685 8693 14664
686 10657 13677
687 10759 16707
688 1338 8282
689 4576 4258
690 9304 20241
691 3449 8632
692 8657 13645
693 4076 7696
694 3317 1283
695 9964 14351
696 14470 17643
697 11396 16320
698 10307 19444
699 10151 12553
700 13095 13020
701 8855 3545
702 9703 19776
703 11887 18060
704 9386 19472
705 3010 7442
706 2753 8059
707 15684 10802
708 15540 10747
709 17123 14485
710 14253 16775
711 15751 11339
712 14312 9790
713 15848 10829
714 5999 2088
715 13307 9986
716 13249 7580
717 15654 11921
718 17205 12835
719 3333 7389
720 648 11151
721 16190 18876
722 3507 2274
723 14955 12176
724 16230 10968
725 10147 15622
726 11540 10218
727 5931 16189
728 11245 14401
729 7204 20264
730 8920 20263
731 17105 14830
732 7538 1302
733 12867 3163
734 11403 1898
735 12270 1678
736 4857 3447
737 10296 7045
738 7567 1360
739 9392 1656
740 13428 15013
741 4766 16739
742 8525 163
743 1402 7101
744 4136 9290
745 1231 8611
746 6658 16603
747 5640 2062
748 11649 11936
749 5864 2693
750 6618 20122
751 8378 3577
752 13568 11795
753 10646 13542
754 11541 16698
755 9986 11760
756 14702 19068
757 3380 1420
758 9644 11369
759 10635 11439
760 11493 18354
761 7052 4146
762 3305 19900
763 4028 12360
764 9290 2578
765 8395 2380
766 10036 7805
767 12899 16307
768 5684 6151
769 10372 16513
770 14528 20705
771 10622 19045
772 12027 20487
773 3893 9680
774 10484 22163
775 15638 11412
776 15920 20778
777 7760 14582
778 12926 17413
779 10046 19248
780 13932 17672
781 9966 18820
782 11114 19232
783 4279 5319
784 12810 5026
785 11860 14329
786 8845 10645
787 10579 10733
788 13951 14710
789 8969 18461
790 5926 16332
791 9225 18241
792 12502 17360
793 6667 20950
794 8588 19919
795 15239 20308
796 7291 21455
797 7813 21185
798 7195 18955
799 8699 19804
800 6340 22871
801 7942 22270
802 6756 21389
803 12339 19014
804 11387 15048
805 6497 20730
806 8591 21326
807 7805 19996
808 9993 17046
809 10317 14781
810 10814 20276
811 13261 16246
812 11408 19426
813 9177 20034
814 11467 12372
815 8934 17937
816 5351 16622
817 6510 14362
818 8835 21930
819 8566 19289
820 14503 17972
821 13124 17123
822 7200 15344
823 12945 21676
824 12741 21291
825 11874 20986
826 10439 15170
827 13262 21877
828 8222 4186
829 14041 21185
830 14480 20233
831 9008 18612
832 9210 17679
833 17353 12253
834 15046 14687
835 5522 16348
836 9724 16044
837 1919 9370
838 3942 18108
839 1400 9220
840 6348 18914
841 14829 16835
842 13413 17903
843 9308 18826
844 13706 19885
845 3144 9364
846 5790 17022
847 8644 9385
848 9134 19347
849 11374 21076
850 13600 13018
851 5554 11327
852 4383 6686
853 2936 5950
854 16135 16610
855 9310 6908
856 9042 9711
857 1940 9277
858 551 8171
859 14087 17591
860 11737 20113
861 2776 7027
862 9949 8092
863 7075 12045
864 2124 8291
865 892 8251
866 17045 12074
867 3257 16372
868 14808 3205
869 13033 4086
870 3737 7244
871 14866 5509
872 14423 984
873 10383 859
874 11433 7980
875 12504 802
876 8789 20285
877 9092 12223
878 10831 15168
879 7847 11159
880 3650 9125
881 4145 7344
882 3464 7121
883 3112 7425
884 9368 5454
885 10576 10214
886 10595 11153
887 4717 7313
888 4535 7564
889 7494 18813
890 6926 15490
891 5515 17076
892 10475 14689
893 1431 6384
894 4401 13680
895 14109 12914
896 1409 11406
897 759 13843
898 6043 19486
899 3007 6882
900 9537 9366
901 8716 16409
902 4559 14232
903 13988 15222
904 10362 15161
905 14581 18492
906 12877 12980
907 16043 15955
908 6144 6788
909 13102 9691
910 14128 11494
911 11558 13532
912 11632 13087
913 16493 15179
914 3415 15834
915 13709 20556
916 13978 17076
917 10344 16632
918 13949 20240
919 9470 19709
920 14066 21406
921 10465 15391
922 13200 20836
923 6837 22434
924 11965 17010
925 9351 21752
926 9257 11329
927 9058 9433
928 14655 11908
929 10711 11991
930 10840 20161
931 7156 20269
932 13852 9985
933 15498 16731
934 12951 10380
935 9904 14632
936 1498 8158
937 11294 5112
938 14265 13153
939 2670 8591
940 6830 5110
941 8192 3353
942 9415 9604
943 1971 9094
944 7184 20454
945 7200 20418
946 1753 7776
947 8712 20977
948 7030 21072
949 2771 8197
950 14396 12886
951 13276 12083
952 3126 8026
953 2698 9449
954 2975 8421
955 11423 13402
956 8446 2623
957 4676 5614
958 12339 19797
959 15715 19417
960 4040 10064
961 11769 16041
962 9763 12122
963 4636 15392
964 9239 9781
965 10529 18544
966 10471 15473
967 3080 8557
968 6357 20087
969 13273 14903
970 6700 3618
971 10215 12423
972 12360 17268
973 8181 18562
974 9026 21813
975 7089 20931
976 3359 9543
977 11253 920
978 2278 8307
979 12122 20606
980 13019 14975
981 10669 16885
982 12801 13068
983 13271 11528
984 11159 13079
985 9636 13358
986 13579 12485
987 4037 6996
988 9901 18951
989 8703 1724
990 6671 4793
991 11880 12787
992 10433 12706
993 12769 15759
994 9421 10146
995 5426 7154
996 11532 17650
997 12320 21077
998 14360 20637
999 11167 20404