use strict;
use warnings;
use threads;
use threads::shared;
use List::Util qw( sum min );

my $glength :shared;

my @dist = <DATA>;
$_ = [ split /\s+/ ] and shift @$_ for @dist;
$glength = 0.5 * sum map { sum @$_ } @dist;

sub path_recursive {
  my( $bound, $len, $path, $end, $tbv, $dist, $in_a_thread ) = @_;

  if( !@$tbv ) {
    $len += $dist->[ $path->[-1] ]->[$end];
    if( $len < $glength ) {
      $glength = $len;
      print "$len: @$path $end ",scalar(localtime),"\n";
    }
    threads->exit() if $in_a_thread;
    return;
  }

  my $last = $dist->[ $path->[-1] ];
  my @sorted = sort { $last->[$a] <=> $last->[$b] } @$tbv;

  for (1..min($bound,@sorted)){
    my $next = shift @sorted;
    if( scalar( threads->list(threads::running) ) < 15 ) {
      threads->create( \&path_recursive, $bound, $len + $last->[$next], [ @$path, $next ], $end, [ @sorted ], $dist, 1 );
    } else {
      path_recursive( $bound, $len + $last->[$next], [ @$path, $next ], $end, [ @sorted ], $dist, 0 );
    }
    push @sorted, $next;
  }
}

path_recursive shift(), 0, [ 1 ], 24, [ 2..23 ], \@dist, 0;
sleep 10 while threads->list(threads::running);

__DATA__