- 论坛徽章:
- 7
|
本帖最后由 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
- #!/usr/bin/perl -w
- # version 26, subversion 0 (v5.26.0)
- use 5.016; # >= 5.016
- my @PITS;
- my @DISTE;
- my $ENDPITS;
- my $MIN;
- my @TAIL;
- my $PATH;
- explore();
- # ____________________SUB____________________
- sub init {
- my %dup;
- my $i = 0;
- while (<DATA>) {
- my ( $a, $b, $d ) = split;
- $dup{$a} //= $i++;
- $dup{$b} //= $i++;
- push @DISTE, [ $dup{$a}, $dup{$b}, $d ];
- }
- @PITS = sort { $dup{$a} <=> $dup{$b} } keys %dup;
- @DISTE = sort { $a->[2] <=> $b->[2] } @DISTE;
- $ENDPITS = @PITS - 1;
- $MIN = $DISTE[-1] * @PITS;
- }
- sub explore {
- init();
- E_( 0, 0, 0 );
- say "\nMIN = $MIN\n";
- echo($PATH);
- }
- sub tail {
- my ( $i, $l, $tail ) = ( @_, 0 );
- $tail += $DISTE[$_][2] for $i .. $i + $ENDPITS - $l - 1;
- $tail;
- }
- sub E_ {
- my ( $n, $b, $sum ) = @_;
- state $MAYBE = [];
- state $quek = [ (0) x @PITS ];
- if ( $n == $ENDPITS ) {
- if ( $MIN > $sum && ok($MAYBE) ) {
- $MIN = $sum;
- $PATH = [@$MAYBE];
- print STDERR "$MIN|";
- }
- return;
- }
- for my $i ( $b .. @DISTE - $ENDPITS + $n ) {
- return if $sum + ( $TAIL[$i][$n] ||= tail( $i, $n ) ) >= $MIN;
- my ( $dit, $dat ) = @{ $DISTE[$i] };
- next if $quek->[$dit] > 1 || $quek->[$dat] > 1;
- $quek->[$dit]++, $quek->[$dat]++;
- $MAYBE->[$n] = $i;
- E_( $n + 1, $i + 1, $sum + $DISTE[$i][2] );
- $quek->[$dit]--, $quek->[$dat]--;
- }
- }
- sub echo {
- my $path = shift;
- ok( $path, 1 );
- }
- sub ok {
- my ( $path, $echo ) = @_;
- my @that;
- for my $p (@$path) {
- my ( $a, $b ) = @{ $DISTE[$p] };
- push @{ $that[$a] }, $b;
- push @{ $that[$b] }, $a;
- }
- my $start;
- for my $t ( 0 .. $#that ) {
- return 0 if not defined $that[$t];
- next if @{ $that[$t] } == 2;
- $start = [$t];
- last;
- }
- my @has;
- my @these;
- my $go = sub {
- my $pits = shift;
- for (@$pits) {
- next if $has[$_];
- push @these, $_;
- $has[$_] = 1;
- __SUB__->( $that[$_] );
- }
- };
- $go->($start);
- return @these == @PITS if !$echo;
- say join ' > ', @PITS[@these];
- }
- __DATA__
- PIT-001 PIT-002 9665
- PIT-001 PIT-003 5794
- PIT-001 PIT-004 96
- PIT-001 PIT-005 5750
- PIT-001 PIT-006 6394
- PIT-001 PIT-007 5750
- PIT-001 PIT-008 3478
- PIT-001 PIT-009 262
- PIT-001 PIT-010 8954
- PIT-001 PIT-011 3751
- PIT-001 PIT-012 5253
- PIT-001 PIT-013 6988
- PIT-001 PIT-014 1364
- PIT-001 PIT-015 9415
- PIT-001 PIT-016 6156
- PIT-001 PIT-017 6015
- PIT-001 PIT-018 7931
- PIT-001 PIT-019 5082
- PIT-001 PIT-020 9891
- PIT-002 PIT-003 6580
- PIT-002 PIT-004 4325
- PIT-002 PIT-005 5355
- PIT-002 PIT-006 7221
- PIT-002 PIT-007 4093
- PIT-002 PIT-008 6098
- PIT-002 PIT-009 2720
- PIT-002 PIT-010 4662
- PIT-002 PIT-011 9336
- PIT-002 PIT-012 378
- PIT-002 PIT-013 4632
- PIT-002 PIT-014 3403
- PIT-002 PIT-015 6736
- PIT-002 PIT-016 7797
- PIT-002 PIT-017 5479
- PIT-002 PIT-018 9189
- PIT-002 PIT-019 1372
- PIT-002 PIT-020 4367
- PIT-003 PIT-004 9601
- PIT-003 PIT-005 6529
- PIT-003 PIT-006 1255
- PIT-003 PIT-007 2524
- PIT-003 PIT-008 5562
- PIT-003 PIT-009 5222
- PIT-003 PIT-010 998
- PIT-003 PIT-011 8214
- PIT-003 PIT-012 3623
- PIT-003 PIT-013 5083
- PIT-003 PIT-014 470
- PIT-003 PIT-015 6274
- PIT-003 PIT-016 7125
- PIT-003 PIT-017 6897
- PIT-003 PIT-018 1281
- PIT-003 PIT-019 9852
- PIT-003 PIT-020 8675
- PIT-004 PIT-005 6886
- PIT-004 PIT-006 456
- PIT-004 PIT-007 4762
- PIT-004 PIT-008 5580
- PIT-004 PIT-009 5893
- PIT-004 PIT-010 3720
- PIT-004 PIT-011 6098
- PIT-004 PIT-012 8211
- PIT-004 PIT-013 7543
- PIT-004 PIT-014 6081
- PIT-004 PIT-015 9590
- PIT-004 PIT-016 4647
- PIT-004 PIT-017 5801
- PIT-004 PIT-018 9606
- PIT-004 PIT-019 2766
- PIT-004 PIT-020 5154
- PIT-005 PIT-006 7815
- PIT-005 PIT-007 3318
- PIT-005 PIT-008 2698
- PIT-005 PIT-009 8343
- PIT-005 PIT-010 3150
- PIT-005 PIT-011 8051
- PIT-005 PIT-012 5387
- PIT-005 PIT-013 5225
- PIT-005 PIT-014 3237
- PIT-005 PIT-015 6158
- PIT-005 PIT-016 2743
- PIT-005 PIT-017 8072
- PIT-005 PIT-018 2154
- PIT-005 PIT-019 7430
- PIT-005 PIT-020 3015
- PIT-006 PIT-007 3927
- PIT-006 PIT-008 970
- PIT-006 PIT-009 5107
- PIT-006 PIT-010 9473
- PIT-006 PIT-011 771
- PIT-006 PIT-012 6491
- PIT-006 PIT-013 33
- PIT-006 PIT-014 5768
- PIT-006 PIT-015 1480
- PIT-006 PIT-016 2144
- PIT-006 PIT-017 3695
- PIT-006 PIT-018 8603
- PIT-006 PIT-019 2669
- PIT-006 PIT-020 4192
- PIT-007 PIT-008 8087
- PIT-007 PIT-009 3979
- PIT-007 PIT-010 3726
- PIT-007 PIT-011 2743
- PIT-007 PIT-012 9232
- PIT-007 PIT-013 217
- PIT-007 PIT-014 4633
- PIT-007 PIT-015 1088
- PIT-007 PIT-016 2993
- PIT-007 PIT-017 3154
- PIT-007 PIT-018 8646
- PIT-007 PIT-019 2484
- PIT-007 PIT-020 4101
- PIT-008 PIT-009 8297
- PIT-008 PIT-010 9313
- PIT-008 PIT-011 4124
- PIT-008 PIT-012 8629
- PIT-008 PIT-013 4267
- PIT-008 PIT-014 7456
- PIT-008 PIT-015 9067
- PIT-008 PIT-016 4293
- PIT-008 PIT-017 7649
- PIT-008 PIT-018 7310
- PIT-008 PIT-019 8391
- PIT-008 PIT-020 3848
- PIT-009 PIT-010 3381
- PIT-009 PIT-011 6493
- PIT-009 PIT-012 4667
- PIT-009 PIT-013 2612
- PIT-009 PIT-014 7146
- PIT-009 PIT-015 9488
- PIT-009 PIT-016 678
- PIT-009 PIT-017 8957
- PIT-009 PIT-018 8025
- PIT-009 PIT-019 1089
- PIT-009 PIT-020 2631
- PIT-010 PIT-011 4976
- PIT-010 PIT-012 5045
- PIT-010 PIT-013 5178
- PIT-010 PIT-014 8014
- PIT-010 PIT-015 5851
- PIT-010 PIT-016 357
- PIT-010 PIT-017 5471
- PIT-010 PIT-018 4935
- PIT-010 PIT-019 9617
- PIT-010 PIT-020 2907
- PIT-011 PIT-012 1515
- PIT-011 PIT-013 1778
- PIT-011 PIT-014 1773
- PIT-011 PIT-015 8704
- PIT-011 PIT-016 3318
- PIT-011 PIT-017 5180
- PIT-011 PIT-018 582
- PIT-011 PIT-019 9573
- PIT-011 PIT-020 7458
- PIT-012 PIT-013 6710
- PIT-012 PIT-014 2171
- PIT-012 PIT-015 9788
- PIT-012 PIT-016 2127
- PIT-012 PIT-017 7630
- PIT-012 PIT-018 8959
- PIT-012 PIT-019 5590
- PIT-012 PIT-020 7108
- PIT-013 PIT-014 9409
- PIT-013 PIT-015 9030
- PIT-013 PIT-016 3654
- PIT-013 PIT-017 714
- PIT-013 PIT-018 118
- PIT-013 PIT-019 7472
- PIT-013 PIT-020 1517
- PIT-014 PIT-015 890
- PIT-014 PIT-016 2776
- PIT-014 PIT-017 7240
- PIT-014 PIT-018 2120
- PIT-014 PIT-019 3314
- PIT-014 PIT-020 7544
- PIT-015 PIT-016 6725
- PIT-015 PIT-017 587
- PIT-015 PIT-018 9877
- PIT-015 PIT-019 1254
- PIT-015 PIT-020 3023
- PIT-016 PIT-017 9444
- PIT-016 PIT-018 5608
- PIT-016 PIT-019 3084
- PIT-016 PIT-020 4228
- PIT-017 PIT-018 7387
- PIT-017 PIT-019 8076
- PIT-017 PIT-020 6686
- PIT-018 PIT-019 5275
- PIT-018 PIT-020 816
- PIT-019 PIT-020 7673
复制代码
v1: perl abc.pl- #!/usr/bin/perl
- my ( $ord, %ord );
- my @dis =
- sort { $a->[1] <=> $b->[1] }
- map {
- my ( $a, $b, $v ) = split;
- $ord{$a} //= $ord++;
- $ord{$b} //= $ord++;
- [ [ $ord{$a}, $ord{$b} ], $v ];
- } <DATA>;
- my $pits = keys %ord;
- my $len = $pits - 1;
- my @inv = sort { $ord{$a} <=> $ord{$b} } keys %ord;
- my @tl = map [ map 0, 1 .. $len ], 1 .. @dis;
- my ( $min, $path ) = $dis[-1][1] * $len;
- sub ok {
- my ( $a, $r, $x ) = @_;
- for my $i ( 0 .. $#$a ) {
- $x = $a->[$i][0], $r = [$i], last if @{ $a->[$i] } <= 1;
- }
- while ( defined $x ) {
- push @$r, $x;
- $x = $a->[$x][ $a->[$x][0] != $r->[-2] ? 0 : 1 ];
- }
- @$r == $pits ? $r : ();
- }
- sub tl {
- my ( $i, $l, $tl ) = ( @_, 0 );
- $tl += $dis[$_][1] for $i .. $i + $len - $l - 1;
- $tl;
- }
- sub go {
- my ( $n, $i, $a, $l, $hd ) = @_;
- if ( $n == 0 ) {
- if ( my $b = ok $a ) {
- $min = $hd;
- $path = $b;
- print STDERR $min, '|';
- }
- return;
- }
- for my $j ( $i .. @dis - $n ) {
- last if $hd + ( $tl[$j][$l] ||= tl $j, $l ) >= $min;
- my ( $A, $B ) = @{ $dis[$j][0] };
- next if @{ $a->[$A] } > 1 or @{ $a->[$B] } > 1;
- my $b = [@$a];
- $b->[$A] = [ @{ $b->[$A] }, $B ];
- $b->[$B] = [ @{ $b->[$B] }, $A ];
- go( $n - 1, $j + 1, $b, $l + 1, $hd + $dis[$j][1] );
- }
- }
- my @now = ( $len, 0, [ map [], 0 .. $len ], 0, 0 );
- go @now;
- print "\nmin = ", $min, $/;
- print join( ' > ', @inv[@$path] ), $/;
- __DATA__
- PIT-001 PIT-002 9665
- PIT-001 PIT-003 5794
- PIT-001 PIT-004 96
- PIT-001 PIT-005 5750
- PIT-001 PIT-006 6394
- PIT-001 PIT-007 5750
- PIT-001 PIT-008 3478
- PIT-001 PIT-009 262
- PIT-001 PIT-010 8954
- PIT-001 PIT-011 3751
- PIT-001 PIT-012 5253
- PIT-001 PIT-013 6988
- PIT-001 PIT-014 1364
- PIT-001 PIT-015 9415
- PIT-001 PIT-016 6156
- PIT-001 PIT-017 6015
- PIT-001 PIT-018 7931
- PIT-001 PIT-019 5082
- PIT-001 PIT-020 9891
- PIT-002 PIT-003 6580
- PIT-002 PIT-004 4325
- PIT-002 PIT-005 5355
- PIT-002 PIT-006 7221
- PIT-002 PIT-007 4093
- PIT-002 PIT-008 6098
- PIT-002 PIT-009 2720
- PIT-002 PIT-010 4662
- PIT-002 PIT-011 9336
- PIT-002 PIT-012 378
- PIT-002 PIT-013 4632
- PIT-002 PIT-014 3403
- PIT-002 PIT-015 6736
- PIT-002 PIT-016 7797
- PIT-002 PIT-017 5479
- PIT-002 PIT-018 9189
- PIT-002 PIT-019 1372
- PIT-002 PIT-020 4367
- PIT-003 PIT-004 9601
- PIT-003 PIT-005 6529
- PIT-003 PIT-006 1255
- PIT-003 PIT-007 2524
- PIT-003 PIT-008 5562
- PIT-003 PIT-009 5222
- PIT-003 PIT-010 998
- PIT-003 PIT-011 8214
- PIT-003 PIT-012 3623
- PIT-003 PIT-013 5083
- PIT-003 PIT-014 470
- PIT-003 PIT-015 6274
- PIT-003 PIT-016 7125
- PIT-003 PIT-017 6897
- PIT-003 PIT-018 1281
- PIT-003 PIT-019 9852
- PIT-003 PIT-020 8675
- PIT-004 PIT-005 6886
- PIT-004 PIT-006 456
- PIT-004 PIT-007 4762
- PIT-004 PIT-008 5580
- PIT-004 PIT-009 5893
- PIT-004 PIT-010 3720
- PIT-004 PIT-011 6098
- PIT-004 PIT-012 8211
- PIT-004 PIT-013 7543
- PIT-004 PIT-014 6081
- PIT-004 PIT-015 9590
- PIT-004 PIT-016 4647
- PIT-004 PIT-017 5801
- PIT-004 PIT-018 9606
- PIT-004 PIT-019 2766
- PIT-004 PIT-020 5154
- PIT-005 PIT-006 7815
- PIT-005 PIT-007 3318
- PIT-005 PIT-008 2698
- PIT-005 PIT-009 8343
- PIT-005 PIT-010 3150
- PIT-005 PIT-011 8051
- PIT-005 PIT-012 5387
- PIT-005 PIT-013 5225
- PIT-005 PIT-014 3237
- PIT-005 PIT-015 6158
- PIT-005 PIT-016 2743
- PIT-005 PIT-017 8072
- PIT-005 PIT-018 2154
- PIT-005 PIT-019 7430
- PIT-005 PIT-020 3015
- PIT-006 PIT-007 3927
- PIT-006 PIT-008 970
- PIT-006 PIT-009 5107
- PIT-006 PIT-010 9473
- PIT-006 PIT-011 771
- PIT-006 PIT-012 6491
- PIT-006 PIT-013 33
- PIT-006 PIT-014 5768
- PIT-006 PIT-015 1480
- PIT-006 PIT-016 2144
- PIT-006 PIT-017 3695
- PIT-006 PIT-018 8603
- PIT-006 PIT-019 2669
- PIT-006 PIT-020 4192
- PIT-007 PIT-008 8087
- PIT-007 PIT-009 3979
- PIT-007 PIT-010 3726
- PIT-007 PIT-011 2743
- PIT-007 PIT-012 9232
- PIT-007 PIT-013 217
- PIT-007 PIT-014 4633
- PIT-007 PIT-015 1088
- PIT-007 PIT-016 2993
- PIT-007 PIT-017 3154
- PIT-007 PIT-018 8646
- PIT-007 PIT-019 2484
- PIT-007 PIT-020 4101
- PIT-008 PIT-009 8297
- PIT-008 PIT-010 9313
- PIT-008 PIT-011 4124
- PIT-008 PIT-012 8629
- PIT-008 PIT-013 4267
- PIT-008 PIT-014 7456
- PIT-008 PIT-015 9067
- PIT-008 PIT-016 4293
- PIT-008 PIT-017 7649
- PIT-008 PIT-018 7310
- PIT-008 PIT-019 8391
- PIT-008 PIT-020 3848
- PIT-009 PIT-010 3381
- PIT-009 PIT-011 6493
- PIT-009 PIT-012 4667
- PIT-009 PIT-013 2612
- PIT-009 PIT-014 7146
- PIT-009 PIT-015 9488
- PIT-009 PIT-016 678
- PIT-009 PIT-017 8957
- PIT-009 PIT-018 8025
- PIT-009 PIT-019 1089
- PIT-009 PIT-020 2631
- PIT-010 PIT-011 4976
- PIT-010 PIT-012 5045
- PIT-010 PIT-013 5178
- PIT-010 PIT-014 8014
- PIT-010 PIT-015 5851
- PIT-010 PIT-016 357
- PIT-010 PIT-017 5471
- PIT-010 PIT-018 4935
- PIT-010 PIT-019 9617
- PIT-010 PIT-020 2907
- PIT-011 PIT-012 1515
- PIT-011 PIT-013 1778
- PIT-011 PIT-014 1773
- PIT-011 PIT-015 8704
- PIT-011 PIT-016 3318
- PIT-011 PIT-017 5180
- PIT-011 PIT-018 582
- PIT-011 PIT-019 9573
- PIT-011 PIT-020 7458
- PIT-012 PIT-013 6710
- PIT-012 PIT-014 2171
- PIT-012 PIT-015 9788
- PIT-012 PIT-016 2127
- PIT-012 PIT-017 7630
- PIT-012 PIT-018 8959
- PIT-012 PIT-019 5590
- PIT-012 PIT-020 7108
- PIT-013 PIT-014 9409
- PIT-013 PIT-015 9030
- PIT-013 PIT-016 3654
- PIT-013 PIT-017 714
- PIT-013 PIT-018 118
- PIT-013 PIT-019 7472
- PIT-013 PIT-020 1517
- PIT-014 PIT-015 890
- PIT-014 PIT-016 2776
- PIT-014 PIT-017 7240
- PIT-014 PIT-018 2120
- PIT-014 PIT-019 3314
- PIT-014 PIT-020 7544
- PIT-015 PIT-016 6725
- PIT-015 PIT-017 587
- PIT-015 PIT-018 9877
- PIT-015 PIT-019 1254
- PIT-015 PIT-020 3023
- PIT-016 PIT-017 9444
- PIT-016 PIT-018 5608
- PIT-016 PIT-019 3084
- PIT-016 PIT-020 4228
- PIT-017 PIT-018 7387
- PIT-017 PIT-019 8076
- PIT-017 PIT-020 6686
- PIT-018 PIT-019 5275
- PIT-018 PIT-020 816
- PIT-019 PIT-020 7673
复制代码 |
|