Chinaunix

标题: 最短的距离 [打印本页]
作者: patagonia2    时间: 2016-05-07 15:44
标题: 最短的距离
遇到这个问题，没什么思路。

请问各位大圣这种情况怎么处理呢。



例如，给出以下距离：

pit-01 ->  pit-02 = 464
pit-01 ->  pit-03 = 518
pit-02 ->  pit-03 = 141

因此，可能的途径有：

pit-01 ->  pit-02 ->  pit-03 = 605
pit-01 ->  pit-03 ->  pit-02 = 659
pit-02 ->  pit-01 ->  pit-03 = 982
pit-02 ->  pit-03 ->  pit-01 = 659
pit-03 ->  pit-02 ->  pit-01 = 605
pit-03 ->  pit-01 ->  pit-02 = 982

所以答案是

pit-01 ->  pit-02 ->  pit-03 = 605


请问各位大圣这种情况怎么处理呢。
  1. PIT-001        PIT-002        9665
  2. PIT-001        PIT-003        5794
  3. PIT-001        PIT-004        96
  4. PIT-001        PIT-005        5750
  5. PIT-001        PIT-006        6394
  6. PIT-001        PIT-007        5750
  7. PIT-001        PIT-008        3478
  8. PIT-001        PIT-009        262
  9. PIT-001        PIT-010        8954
  10. PIT-001        PIT-011        3751
  11. PIT-001        PIT-012        5253
  12. PIT-001        PIT-013        6988
  13. PIT-001        PIT-014        1364
  14. PIT-001        PIT-015        9415
  15. PIT-001        PIT-016        6156
  16. PIT-001        PIT-017        6015
  17. PIT-001        PIT-018        7931
  18. PIT-001        PIT-019        5082
  19. PIT-001        PIT-020        9891
  20. PIT-002        PIT-003        6580
  21. PIT-002        PIT-004        4325
  22. PIT-002        PIT-005        5355
  23. PIT-002        PIT-006        7221
  24. PIT-002        PIT-007        4093
  25. PIT-002        PIT-008        6098
  26. PIT-002        PIT-009        2720
  27. PIT-002        PIT-010        4662
  28. PIT-002        PIT-011        9336
  29. PIT-002        PIT-012        378
  30. PIT-002        PIT-013        4632
  31. PIT-002        PIT-014        3403
  32. PIT-002        PIT-015        6736
  33. PIT-002        PIT-016        7797
  34. PIT-002        PIT-017        5479
  35. PIT-002        PIT-018        9189
  36. PIT-002        PIT-019        1372
  37. PIT-002        PIT-020        4367
  38. PIT-003        PIT-004        9601
  39. PIT-003        PIT-005        6529
  40. PIT-003        PIT-006        1255
  41. PIT-003        PIT-007        2524
  42. PIT-003        PIT-008        5562
  43. PIT-003        PIT-009        5222
  44. PIT-003        PIT-010        998
  45. PIT-003        PIT-011        8214
  46. PIT-003        PIT-012        3623
  47. PIT-003        PIT-013        5083
  48. PIT-003        PIT-014        470
  49. PIT-003        PIT-015        6274
  50. PIT-003        PIT-016        7125
  51. PIT-003        PIT-017        6897
  52. PIT-003        PIT-018        1281
  53. PIT-003        PIT-019        9852
  54. PIT-003        PIT-020        8675
  55. PIT-004        PIT-005        6886
  56. PIT-004        PIT-006        456
  57. PIT-004        PIT-007        4762
  58. PIT-004        PIT-008        5580
  59. PIT-004        PIT-009        5893
  60. PIT-004        PIT-010        3720
  61. PIT-004        PIT-011        6098
  62. PIT-004        PIT-012        8211
  63. PIT-004        PIT-013        7543
  64. PIT-004        PIT-014        6081
  65. PIT-004        PIT-015        9590
  66. PIT-004        PIT-016        4647
  67. PIT-004        PIT-017        5801
  68. PIT-004        PIT-018        9606
  69. PIT-004        PIT-019        2766
  70. PIT-004        PIT-020        5154
  71. PIT-005        PIT-006        7815
  72. PIT-005        PIT-007        3318
  73. PIT-005        PIT-008        2698
  74. PIT-005        PIT-009        8343
  75. PIT-005        PIT-010        3150
  76. PIT-005        PIT-011        8051
  77. PIT-005        PIT-012        5387
  78. PIT-005        PIT-013        5225
  79. PIT-005        PIT-014        3237
  80. PIT-005        PIT-015        6158
  81. PIT-005        PIT-016        2743
  82. PIT-005        PIT-017        8072
  83. PIT-005        PIT-018        2154
  84. PIT-005        PIT-019        7430
  85. PIT-005        PIT-020        3015
  86. PIT-006        PIT-007        3927
  87. PIT-006        PIT-008        970
  88. PIT-006        PIT-009        5107
  89. PIT-006        PIT-010        9473
  90. PIT-006        PIT-011        771
  91. PIT-006        PIT-012        6491
  92. PIT-006        PIT-013        33
  93. PIT-006        PIT-014        5768
  94. PIT-006        PIT-015        1480
  95. PIT-006        PIT-016        2144
  96. PIT-006        PIT-017        3695
  97. PIT-006        PIT-018        8603
  98. PIT-006        PIT-019        2669
  99. PIT-006        PIT-020        4192
  100. PIT-007        PIT-008        8087
  101. PIT-007        PIT-009        3979
  102. PIT-007        PIT-010        3726
  103. PIT-007        PIT-011        2743
  104. PIT-007        PIT-012        9232
  105. PIT-007        PIT-013        217
  106. PIT-007        PIT-014        4633
  107. PIT-007        PIT-015        1088
  108. PIT-007        PIT-016        2993
  109. PIT-007        PIT-017        3154
  110. PIT-007        PIT-018        8646
  111. PIT-007        PIT-019        2484
  112. PIT-007        PIT-020        4101
  113. PIT-008        PIT-009        8297
  114. PIT-008        PIT-010        9313
  115. PIT-008        PIT-011        4124
  116. PIT-008        PIT-012        8629
  117. PIT-008        PIT-013        4267
  118. PIT-008        PIT-014        7456
  119. PIT-008        PIT-015        9067
  120. PIT-008        PIT-016        4293
  121. PIT-008        PIT-017        7649
  122. PIT-008        PIT-018        7310
  123. PIT-008        PIT-019        8391
  124. PIT-008        PIT-020        3848
  125. PIT-009        PIT-010        3381
  126. PIT-009        PIT-011        6493
  127. PIT-009        PIT-012        4667
  128. PIT-009        PIT-013        2612
  129. PIT-009        PIT-014        7146
  130. PIT-009        PIT-015        9488
  131. PIT-009        PIT-016        678
  132. PIT-009        PIT-017        8957
  133. PIT-009        PIT-018        8025
  134. PIT-009        PIT-019        1089
  135. PIT-009        PIT-020        2631
  136. PIT-010        PIT-011        4976
  137. PIT-010        PIT-012        5045
  138. PIT-010        PIT-013        5178
  139. PIT-010        PIT-014        8014
  140. PIT-010        PIT-015        5851
  141. PIT-010        PIT-016        357
  142. PIT-010        PIT-017        5471
  143. PIT-010        PIT-018        4935
  144. PIT-010        PIT-019        9617
  145. PIT-010        PIT-020        2907
  146. PIT-011        PIT-012        1515
  147. PIT-011        PIT-013        1778
  148. PIT-011        PIT-014        1773
  149. PIT-011        PIT-015        8704
  150. PIT-011        PIT-016        3318
  151. PIT-011        PIT-017        5180
  152. PIT-011        PIT-018        582
  153. PIT-011        PIT-019        9573
  154. PIT-011        PIT-020        7458
  155. PIT-012        PIT-013        6710
  156. PIT-012        PIT-014        2171
  157. PIT-012        PIT-015        9788
  158. PIT-012        PIT-016        2127
  159. PIT-012        PIT-017        7630
  160. PIT-012        PIT-018        8959
  161. PIT-012        PIT-019        5590
  162. PIT-012        PIT-020        7108
  163. PIT-013        PIT-014        9409
  164. PIT-013        PIT-015        9030
  165. PIT-013        PIT-016        3654
  166. PIT-013        PIT-017        714
  167. PIT-013        PIT-018        118
  168. PIT-013        PIT-019        7472
  169. PIT-013        PIT-020        1517
  170. PIT-014        PIT-015        890
  171. PIT-014        PIT-016        2776
  172. PIT-014        PIT-017        7240
  173. PIT-014        PIT-018        2120
  174. PIT-014        PIT-019        3314
  175. PIT-014        PIT-020        7544
  176. PIT-015        PIT-016        6725
  177. PIT-015        PIT-017        587
  178. PIT-015        PIT-018        9877
  179. PIT-015        PIT-019        1254
  180. PIT-015        PIT-020        3023
  181. PIT-016        PIT-017        9444
  182. PIT-016        PIT-018        5608
  183. PIT-016        PIT-019        3084
  184. PIT-016        PIT-020        4228
  185. PIT-017        PIT-018        7387
  186. PIT-017        PIT-019        8076
  187. PIT-017        PIT-020        6686
  188. PIT-018        PIT-019        5275
  189. PIT-018        PIT-020        816
  190. PIT-019        PIT-020        7673
复制代码
作者: tolilong    时间: 2016-05-07 15:48
本帖最后由 tolilong 于 2016-05-07 15:49 编辑

已经所有点的距离？
作者: mswsg    时间: 2016-05-07 17:20
本帖最后由 mswsg 于 2016-05-07 17:26 编辑

求大神。。！这个看了一会
一共有20个点， 要求一次经过每个点（点不重复），并且总距离最短。
已经给出任意每个点之间的距离（a,b）=x
第一个点的可能性是20，依次是19 ，18 ，... 3,2,1
。。。。。
作者: Herowinter    时间: 2016-05-07 18:17
求一条路径最短的哈密尔顿回路，这种题目用shell来解，
真的合适吗？
作者: patagonia2    时间: 2016-05-09 18:04
回复 2# tolilong


     谢谢大圣指导。
作者: patagonia2    时间: 2016-05-09 18:05
回复 3# mswsg

谢谢大神指导。
大神们什么好的代码？
   
作者: patagonia2    时间: 2016-05-09 18:08
回复 4# Herowinter


这数据量也不大，大圣来一发
谢谢大圣指导。
作者: Herowinter    时间: 2016-05-09 18:16
回复 7# patagonia2

这个问题远比你想象的复杂, 我算法没学好, 写不来.

维基百科:
寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度为O(n!*n)暴力搜索。
利用状态压缩动态规划，可以将时间复杂度降低到O(2^n*n^3)。
n=20, 优化算法也不简单.

你可以把这题发到一些高级语言的版块(如C++  Java)等, 看看有没有大神能帮你.
   
作者: patagonia2    时间: 2016-05-10 15:42
回复 8# Herowinter

谢谢大圣指导。
作者: lll1985911    时间: 2016-05-10 20:51
百度文库中搜了一篇文章（关于物流系统方面的）可能有点帮助。
（我没有发url的权限）

这个是较为典型的哈密尔顿回路问题。
参考A*算法和Dijkstra应该会有一些提示。
严格的说，shell不说不能做，而是shell天生并不是解决这类复杂问题的。

另外针对现代物流系统，我个人认为不能只单单考虑路径长短，货物装卸，堵车概率，海拔高低，都是影响运行成本的因素。
作者: patagonia2    时间: 2016-05-17 17:29
回复 10# lll1985911

谢谢大圣指导
   
作者: rubyish    时间: 2016-05-29 05:41
本帖最后由 rubyish 于 2017-10-01 20:16 编辑

maybe

output:

21090|20377|19194|17904|17809|16540|
MIN = 16540

PIT-005 > PIT-008 > PIT-006 > PIT-004 > PIT-001 > PIT-009 > PIT-016 > PIT-010 > PIT-003 > PIT-014 > PIT-015 > PIT-017 > PIT-013 > PIT-007 > PIT-019 > PIT-002 > PIT-012 > PIT-011 > PIT-018 > PIT-020

v1: time 2.25s
v2: time 1.35s

v2: perl abc.pl

  1. #!/usr/bin/perl -w
  2. # version 26, subversion 0 (v5.26.0)
  3. use 5.016;    # >= 5.016

  5. my @PITS;
  6. my @DISTE;
  7. my $ENDPITS;
  8. my $MIN;
  9. my @TAIL;
  10. my $PATH;

  12. explore();

  14. # ____________________SUB____________________
  15. sub init {
  16.     my %dup;
  17.     my $i = 0;
  18.     while (<DATA>) {
  19.         my ( $a, $b, $d ) = split;
  20.         $dup{$a} //= $i++;
  21.         $dup{$b} //= $i++;
  22.         push @DISTE, [ $dup{$a}, $dup{$b}, $d ];
  23.     }
  24.     @PITS  = sort { $dup{$a} <=> $dup{$b} } keys %dup;
  25.     @DISTE = sort { $a->[2] <=> $b->[2] } @DISTE;
  26.     $ENDPITS = @PITS - 1;
  27.     $MIN     = $DISTE[-1] * @PITS;
  28. }

  30. sub explore {
  31.     init();
  32.     E_( 0, 0, 0 );
  33.     say "\nMIN = $MIN\n";
  34.     echo($PATH);
  35. }

  37. sub tail {
  38.     my ( $i, $l, $tail ) = ( @_, 0 );
  39.     $tail += $DISTE[$_][2] for $i .. $i + $ENDPITS - $l - 1;
  40.     $tail;
  41. }

  43. sub E_ {
  44.     my ( $n, $b, $sum ) = @_;
  45.     state $MAYBE = [];
  46.     state $quek = [ (0) x @PITS ];

  48.     if ( $n == $ENDPITS ) {
  49.         if ( $MIN > $sum && ok($MAYBE) ) {
  50.             $MIN  = $sum;
  51.             $PATH = [@$MAYBE];
  52.             print STDERR "$MIN|";
  53.         }
  54.         return;
  55.     }

  57.     for my $i ( $b .. @DISTE - $ENDPITS + $n ) {
  58.         return if $sum + ( $TAIL[$i][$n] ||= tail( $i, $n ) ) >= $MIN;

  60.         my ( $dit, $dat ) = @{ $DISTE[$i] };

  62.         next if $quek->[$dit] > 1 || $quek->[$dat] > 1;
  63.         $quek->[$dit]++, $quek->[$dat]++;
  64.         $MAYBE->[$n] = $i;
  65.         E_( $n + 1, $i + 1, $sum + $DISTE[$i][2] );
  66.         $quek->[$dit]--, $quek->[$dat]--;
  67.     }
  68. }

  70. sub echo {
  71.     my $path = shift;
  72.     ok( $path, 1 );
  73. }

  75. sub ok {
  76.     my ( $path, $echo ) = @_;
  77.     my @that;
  78.     for my $p (@$path) {
  79.         my ( $a, $b ) = @{ $DISTE[$p] };
  80.         push @{ $that[$a] }, $b;
  81.         push @{ $that[$b] }, $a;
  82.     }

  84.     my $start;
  85.     for my $t ( 0 .. $#that ) {
  86.         return 0 if not defined $that[$t];
  87.         next if @{ $that[$t] } == 2;
  88.         $start = [$t];
  89.         last;
  90.     }

  92.     my @has;
  93.     my @these;

  95.     my $go = sub {
  96.         my $pits = shift;
  97.         for (@$pits) {
  98.             next if $has[$_];
  99.             push @these, $_;
  100.             $has[$_] = 1;
  101.             __SUB__->( $that[$_] );
  102.         }
  103.     };
  104.     $go->($start);
  105.     return @these == @PITS if !$echo;
  106.     say join ' > ', @PITS[@these];
  107. }

  109. __DATA__
  110. PIT-001 PIT-002 9665
  111. PIT-001 PIT-003 5794
  112. PIT-001 PIT-004 96
  113. PIT-001 PIT-005 5750
  114. PIT-001 PIT-006 6394
  115. PIT-001 PIT-007 5750
  116. PIT-001 PIT-008 3478
  117. PIT-001 PIT-009 262
  118. PIT-001 PIT-010 8954
  119. PIT-001 PIT-011 3751
  120. PIT-001 PIT-012 5253
  121. PIT-001 PIT-013 6988
  122. PIT-001 PIT-014 1364
  123. PIT-001 PIT-015 9415
  124. PIT-001 PIT-016 6156
  125. PIT-001 PIT-017 6015
  126. PIT-001 PIT-018 7931
  127. PIT-001 PIT-019 5082
  128. PIT-001 PIT-020 9891
  129. PIT-002 PIT-003 6580
  130. PIT-002 PIT-004 4325
  131. PIT-002 PIT-005 5355
  132. PIT-002 PIT-006 7221
  133. PIT-002 PIT-007 4093
  134. PIT-002 PIT-008 6098
  135. PIT-002 PIT-009 2720
  136. PIT-002 PIT-010 4662
  137. PIT-002 PIT-011 9336
  138. PIT-002 PIT-012 378
  139. PIT-002 PIT-013 4632
  140. PIT-002 PIT-014 3403
  141. PIT-002 PIT-015 6736
  142. PIT-002 PIT-016 7797
  143. PIT-002 PIT-017 5479
  144. PIT-002 PIT-018 9189
  145. PIT-002 PIT-019 1372
  146. PIT-002 PIT-020 4367
  147. PIT-003 PIT-004 9601
  148. PIT-003 PIT-005 6529
  149. PIT-003 PIT-006 1255
  150. PIT-003 PIT-007 2524
  151. PIT-003 PIT-008 5562
  152. PIT-003 PIT-009 5222
  153. PIT-003 PIT-010 998
  154. PIT-003 PIT-011 8214
  155. PIT-003 PIT-012 3623
  156. PIT-003 PIT-013 5083
  157. PIT-003 PIT-014 470
  158. PIT-003 PIT-015 6274
  159. PIT-003 PIT-016 7125
  160. PIT-003 PIT-017 6897
  161. PIT-003 PIT-018 1281
  162. PIT-003 PIT-019 9852
  163. PIT-003 PIT-020 8675
  164. PIT-004 PIT-005 6886
  165. PIT-004 PIT-006 456
  166. PIT-004 PIT-007 4762
  167. PIT-004 PIT-008 5580
  168. PIT-004 PIT-009 5893
  169. PIT-004 PIT-010 3720
  170. PIT-004 PIT-011 6098
  171. PIT-004 PIT-012 8211
  172. PIT-004 PIT-013 7543
  173. PIT-004 PIT-014 6081
  174. PIT-004 PIT-015 9590
  175. PIT-004 PIT-016 4647
  176. PIT-004 PIT-017 5801
  177. PIT-004 PIT-018 9606
  178. PIT-004 PIT-019 2766
  179. PIT-004 PIT-020 5154
  180. PIT-005 PIT-006 7815
  181. PIT-005 PIT-007 3318
  182. PIT-005 PIT-008 2698
  183. PIT-005 PIT-009 8343
  184. PIT-005 PIT-010 3150
  185. PIT-005 PIT-011 8051
  186. PIT-005 PIT-012 5387
  187. PIT-005 PIT-013 5225
  188. PIT-005 PIT-014 3237
  189. PIT-005 PIT-015 6158
  190. PIT-005 PIT-016 2743
  191. PIT-005 PIT-017 8072
  192. PIT-005 PIT-018 2154
  193. PIT-005 PIT-019 7430
  194. PIT-005 PIT-020 3015
  195. PIT-006 PIT-007 3927
  196. PIT-006 PIT-008 970
  197. PIT-006 PIT-009 5107
  198. PIT-006 PIT-010 9473
  199. PIT-006 PIT-011 771
  200. PIT-006 PIT-012 6491
  201. PIT-006 PIT-013 33
  202. PIT-006 PIT-014 5768
  203. PIT-006 PIT-015 1480
  204. PIT-006 PIT-016 2144
  205. PIT-006 PIT-017 3695
  206. PIT-006 PIT-018 8603
  207. PIT-006 PIT-019 2669
  208. PIT-006 PIT-020 4192
  209. PIT-007 PIT-008 8087
  210. PIT-007 PIT-009 3979
  211. PIT-007 PIT-010 3726
  212. PIT-007 PIT-011 2743
  213. PIT-007 PIT-012 9232
  214. PIT-007 PIT-013 217
  215. PIT-007 PIT-014 4633
  216. PIT-007 PIT-015 1088
  217. PIT-007 PIT-016 2993
  218. PIT-007 PIT-017 3154
  219. PIT-007 PIT-018 8646
  220. PIT-007 PIT-019 2484
  221. PIT-007 PIT-020 4101
  222. PIT-008 PIT-009 8297
  223. PIT-008 PIT-010 9313
  224. PIT-008 PIT-011 4124
  225. PIT-008 PIT-012 8629
  226. PIT-008 PIT-013 4267
  227. PIT-008 PIT-014 7456
  228. PIT-008 PIT-015 9067
  229. PIT-008 PIT-016 4293
  230. PIT-008 PIT-017 7649
  231. PIT-008 PIT-018 7310
  232. PIT-008 PIT-019 8391
  233. PIT-008 PIT-020 3848
  234. PIT-009 PIT-010 3381
  235. PIT-009 PIT-011 6493
  236. PIT-009 PIT-012 4667
  237. PIT-009 PIT-013 2612
  238. PIT-009 PIT-014 7146
  239. PIT-009 PIT-015 9488
  240. PIT-009 PIT-016 678
  241. PIT-009 PIT-017 8957
  242. PIT-009 PIT-018 8025
  243. PIT-009 PIT-019 1089
  244. PIT-009 PIT-020 2631
  245. PIT-010 PIT-011 4976
  246. PIT-010 PIT-012 5045
  247. PIT-010 PIT-013 5178
  248. PIT-010 PIT-014 8014
  249. PIT-010 PIT-015 5851
  250. PIT-010 PIT-016 357
  251. PIT-010 PIT-017 5471
  252. PIT-010 PIT-018 4935
  253. PIT-010 PIT-019 9617
  254. PIT-010 PIT-020 2907
  255. PIT-011 PIT-012 1515
  256. PIT-011 PIT-013 1778
  257. PIT-011 PIT-014 1773
  258. PIT-011 PIT-015 8704
  259. PIT-011 PIT-016 3318
  260. PIT-011 PIT-017 5180
  261. PIT-011 PIT-018 582
  262. PIT-011 PIT-019 9573
  263. PIT-011 PIT-020 7458
  264. PIT-012 PIT-013 6710
  265. PIT-012 PIT-014 2171
  266. PIT-012 PIT-015 9788
  267. PIT-012 PIT-016 2127
  268. PIT-012 PIT-017 7630
  269. PIT-012 PIT-018 8959
  270. PIT-012 PIT-019 5590
  271. PIT-012 PIT-020 7108
  272. PIT-013 PIT-014 9409
  273. PIT-013 PIT-015 9030
  274. PIT-013 PIT-016 3654
  275. PIT-013 PIT-017 714
  276. PIT-013 PIT-018 118
  277. PIT-013 PIT-019 7472
  278. PIT-013 PIT-020 1517
  279. PIT-014 PIT-015 890
  280. PIT-014 PIT-016 2776
  281. PIT-014 PIT-017 7240
  282. PIT-014 PIT-018 2120
  283. PIT-014 PIT-019 3314
  284. PIT-014 PIT-020 7544
  285. PIT-015 PIT-016 6725
  286. PIT-015 PIT-017 587
  287. PIT-015 PIT-018 9877
  288. PIT-015 PIT-019 1254
  289. PIT-015 PIT-020 3023
  290. PIT-016 PIT-017 9444
  291. PIT-016 PIT-018 5608
  292. PIT-016 PIT-019 3084
  293. PIT-016 PIT-020 4228
  294. PIT-017 PIT-018 7387
  295. PIT-017 PIT-019 8076
  296. PIT-017 PIT-020 6686
  297. PIT-018 PIT-019 5275
  298. PIT-018 PIT-020 816
  299. PIT-019 PIT-020 7673
复制代码





v1: perl abc.pl
  1. #!/usr/bin/perl

  3. my ( $ord, %ord );
  4. my @dis =
  5.   sort { $a->[1] <=> $b->[1] }
  6.   map {
  7.     my ( $a, $b, $v ) = split;
  8.     $ord{$a} //= $ord++;
  9.     $ord{$b} //= $ord++;
  10.     [ [ $ord{$a}, $ord{$b} ], $v ];
  11.   } <DATA>;

  13. my $pits = keys %ord;
  14. my $len  = $pits - 1;
  15. my @inv  = sort { $ord{$a} <=> $ord{$b} } keys %ord;
  16. my @tl   = map [ map 0, 1 .. $len ], 1 .. @dis;
  17. my ( $min, $path ) = $dis[-1][1] * $len;

  19. sub ok {
  20.     my ( $a, $r, $x ) = @_;
  21.     for my $i ( 0 .. $#$a ) {
  22.         $x = $a->[$i][0], $r = [$i], last if @{ $a->[$i] } <= 1;
  23.     }
  24.     while ( defined $x ) {
  25.         push @$r, $x;
  26.         $x = $a->[$x][ $a->[$x][0] != $r->[-2] ? 0 : 1 ];
  27.     }
  28.     @$r == $pits ? $r : ();
  29. }

  31. sub tl {
  32.     my ( $i, $l, $tl ) = ( @_, 0 );
  33.     $tl += $dis[$_][1] for $i .. $i + $len - $l - 1;
  34.     $tl;
  35. }

  37. sub go {
  38.     my ( $n, $i, $a, $l, $hd ) = @_;
  39.     if ( $n == 0 ) {
  40.         if ( my $b = ok $a ) {
  41.             $min  = $hd;
  42.             $path = $b;
  43.             print STDERR $min, '|';
  44.         }
  45.         return;
  46.     }

  48.     for my $j ( $i .. @dis - $n ) {
  49.         last if $hd + ( $tl[$j][$l] ||= tl $j, $l ) >= $min;
  50.         my ( $A, $B ) = @{ $dis[$j][0] };
  51.         next if @{ $a->[$A] } > 1 or @{ $a->[$B] } > 1;
  52.         my $b = [@$a];
  53.         $b->[$A] = [ @{ $b->[$A] }, $B ];
  54.         $b->[$B] = [ @{ $b->[$B] }, $A ];
  55.         go( $n - 1, $j + 1, $b, $l + 1, $hd + $dis[$j][1] );
  56.     }
  57. }

  59. my @now = ( $len, 0, [ map [], 0 .. $len ], 0, 0 );
  60. go @now;
  61. print "\nmin = ", $min, $/;
  62. print join( ' > ', @inv[@$path] ), $/;

  64. __DATA__
  65. PIT-001 PIT-002 9665
  66. PIT-001 PIT-003 5794
  67. PIT-001 PIT-004 96
  68. PIT-001 PIT-005 5750
  69. PIT-001 PIT-006 6394
  70. PIT-001 PIT-007 5750
  71. PIT-001 PIT-008 3478
  72. PIT-001 PIT-009 262
  73. PIT-001 PIT-010 8954
  74. PIT-001 PIT-011 3751
  75. PIT-001 PIT-012 5253
  76. PIT-001 PIT-013 6988
  77. PIT-001 PIT-014 1364
  78. PIT-001 PIT-015 9415
  79. PIT-001 PIT-016 6156
  80. PIT-001 PIT-017 6015
  81. PIT-001 PIT-018 7931
  82. PIT-001 PIT-019 5082
  83. PIT-001 PIT-020 9891
  84. PIT-002 PIT-003 6580
  85. PIT-002 PIT-004 4325
  86. PIT-002 PIT-005 5355
  87. PIT-002 PIT-006 7221
  88. PIT-002 PIT-007 4093
  89. PIT-002 PIT-008 6098
  90. PIT-002 PIT-009 2720
  91. PIT-002 PIT-010 4662
  92. PIT-002 PIT-011 9336
  93. PIT-002 PIT-012 378
  94. PIT-002 PIT-013 4632
  95. PIT-002 PIT-014 3403
  96. PIT-002 PIT-015 6736
  97. PIT-002 PIT-016 7797
  98. PIT-002 PIT-017 5479
  99. PIT-002 PIT-018 9189
  100. PIT-002 PIT-019 1372
  101. PIT-002 PIT-020 4367
  102. PIT-003 PIT-004 9601
  103. PIT-003 PIT-005 6529
  104. PIT-003 PIT-006 1255
  105. PIT-003 PIT-007 2524
  106. PIT-003 PIT-008 5562
  107. PIT-003 PIT-009 5222
  108. PIT-003 PIT-010 998
  109. PIT-003 PIT-011 8214
  110. PIT-003 PIT-012 3623
  111. PIT-003 PIT-013 5083
  112. PIT-003 PIT-014 470
  113. PIT-003 PIT-015 6274
  114. PIT-003 PIT-016 7125
  115. PIT-003 PIT-017 6897
  116. PIT-003 PIT-018 1281
  117. PIT-003 PIT-019 9852
  118. PIT-003 PIT-020 8675
  119. PIT-004 PIT-005 6886
  120. PIT-004 PIT-006 456
  121. PIT-004 PIT-007 4762
  122. PIT-004 PIT-008 5580
  123. PIT-004 PIT-009 5893
  124. PIT-004 PIT-010 3720
  125. PIT-004 PIT-011 6098
  126. PIT-004 PIT-012 8211
  127. PIT-004 PIT-013 7543
  128. PIT-004 PIT-014 6081
  129. PIT-004 PIT-015 9590
  130. PIT-004 PIT-016 4647
  131. PIT-004 PIT-017 5801
  132. PIT-004 PIT-018 9606
  133. PIT-004 PIT-019 2766
  134. PIT-004 PIT-020 5154
  135. PIT-005 PIT-006 7815
  136. PIT-005 PIT-007 3318
  137. PIT-005 PIT-008 2698
  138. PIT-005 PIT-009 8343
  139. PIT-005 PIT-010 3150
  140. PIT-005 PIT-011 8051
  141. PIT-005 PIT-012 5387
  142. PIT-005 PIT-013 5225
  143. PIT-005 PIT-014 3237
  144. PIT-005 PIT-015 6158
  145. PIT-005 PIT-016 2743
  146. PIT-005 PIT-017 8072
  147. PIT-005 PIT-018 2154
  148. PIT-005 PIT-019 7430
  149. PIT-005 PIT-020 3015
  150. PIT-006 PIT-007 3927
  151. PIT-006 PIT-008 970
  152. PIT-006 PIT-009 5107
  153. PIT-006 PIT-010 9473
  154. PIT-006 PIT-011 771
  155. PIT-006 PIT-012 6491
  156. PIT-006 PIT-013 33
  157. PIT-006 PIT-014 5768
  158. PIT-006 PIT-015 1480
  159. PIT-006 PIT-016 2144
  160. PIT-006 PIT-017 3695
  161. PIT-006 PIT-018 8603
  162. PIT-006 PIT-019 2669
  163. PIT-006 PIT-020 4192
  164. PIT-007 PIT-008 8087
  165. PIT-007 PIT-009 3979
  166. PIT-007 PIT-010 3726
  167. PIT-007 PIT-011 2743
  168. PIT-007 PIT-012 9232
  169. PIT-007 PIT-013 217
  170. PIT-007 PIT-014 4633
  171. PIT-007 PIT-015 1088
  172. PIT-007 PIT-016 2993
  173. PIT-007 PIT-017 3154
  174. PIT-007 PIT-018 8646
  175. PIT-007 PIT-019 2484
  176. PIT-007 PIT-020 4101
  177. PIT-008 PIT-009 8297
  178. PIT-008 PIT-010 9313
  179. PIT-008 PIT-011 4124
  180. PIT-008 PIT-012 8629
  181. PIT-008 PIT-013 4267
  182. PIT-008 PIT-014 7456
  183. PIT-008 PIT-015 9067
  184. PIT-008 PIT-016 4293
  185. PIT-008 PIT-017 7649
  186. PIT-008 PIT-018 7310
  187. PIT-008 PIT-019 8391
  188. PIT-008 PIT-020 3848
  189. PIT-009 PIT-010 3381
  190. PIT-009 PIT-011 6493
  191. PIT-009 PIT-012 4667
  192. PIT-009 PIT-013 2612
  193. PIT-009 PIT-014 7146
  194. PIT-009 PIT-015 9488
  195. PIT-009 PIT-016 678
  196. PIT-009 PIT-017 8957
  197. PIT-009 PIT-018 8025
  198. PIT-009 PIT-019 1089
  199. PIT-009 PIT-020 2631
  200. PIT-010 PIT-011 4976
  201. PIT-010 PIT-012 5045
  202. PIT-010 PIT-013 5178
  203. PIT-010 PIT-014 8014
  204. PIT-010 PIT-015 5851
  205. PIT-010 PIT-016 357
  206. PIT-010 PIT-017 5471
  207. PIT-010 PIT-018 4935
  208. PIT-010 PIT-019 9617
  209. PIT-010 PIT-020 2907
  210. PIT-011 PIT-012 1515
  211. PIT-011 PIT-013 1778
  212. PIT-011 PIT-014 1773
  213. PIT-011 PIT-015 8704
  214. PIT-011 PIT-016 3318
  215. PIT-011 PIT-017 5180
  216. PIT-011 PIT-018 582
  217. PIT-011 PIT-019 9573
  218. PIT-011 PIT-020 7458
  219. PIT-012 PIT-013 6710
  220. PIT-012 PIT-014 2171
  221. PIT-012 PIT-015 9788
  222. PIT-012 PIT-016 2127
  223. PIT-012 PIT-017 7630
  224. PIT-012 PIT-018 8959
  225. PIT-012 PIT-019 5590
  226. PIT-012 PIT-020 7108
  227. PIT-013 PIT-014 9409
  228. PIT-013 PIT-015 9030
  229. PIT-013 PIT-016 3654
  230. PIT-013 PIT-017 714
  231. PIT-013 PIT-018 118
  232. PIT-013 PIT-019 7472
  233. PIT-013 PIT-020 1517
  234. PIT-014 PIT-015 890
  235. PIT-014 PIT-016 2776
  236. PIT-014 PIT-017 7240
  237. PIT-014 PIT-018 2120
  238. PIT-014 PIT-019 3314
  239. PIT-014 PIT-020 7544
  240. PIT-015 PIT-016 6725
  241. PIT-015 PIT-017 587
  242. PIT-015 PIT-018 9877
  243. PIT-015 PIT-019 1254
  244. PIT-015 PIT-020 3023
  245. PIT-016 PIT-017 9444
  246. PIT-016 PIT-018 5608
  247. PIT-016 PIT-019 3084
  248. PIT-016 PIT-020 4228
  249. PIT-017 PIT-018 7387
  250. PIT-017 PIT-019 8076
  251. PIT-017 PIT-020 6686
  252. PIT-018 PIT-019 5275
  253. PIT-018 PIT-020 816
  254. PIT-019 PIT-020 7673
复制代码
作者: 523066680    时间: 2021-10-10 14:10
回复 12# rubyish

Hi Rubyish你的邮箱是多少? 或者有QQ/微信之类的联系方式吗？




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2