#! perl -slw
use strict;
use threads;
use threads::shared;
use List::Util qw( sum min );

my $running :shared = 0;
my $glength :shared;

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

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

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

    for( 1 .. min( $bound, scalar( @sorted ) ) ){
        my $next = shift @sorted;
        _path_recursive( $bound, $len + $last->[$next], [ @$path, $next ], $end, [ @sorted ], $dist );
        push @sorted, $next;
    }
}

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

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

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

    for( 1 .. min( $bound, scalar( @sorted ) ) ){
        my $next = shift @sorted;
        sleep 1 while $running > 3;
        async {
            { lock $running; ++$running; }
            my $tid = threads->tid;
            print "[$tid] started";
            _path_recursive( $bound, $len + $last->[$next], [ @$path, $next ], $end, [ @sorted ], $dist );
            { lock $running; --$running; }
            print "[$tid] ended";
        }->detach;
        sleep 1; ## give the thread a timeslice to get going.
        push @sorted, $next;
    }
    sleep 1 while $running;
}

my @dist = <DATA>;
$_ = [ split /\s+/ ] and shift @$_ for @dist;
$glength = 0.5 * sum map { sum @$_ } @dist;
path_recursive shift(), 0, [ 1 ], 24, [ 2..23 ], \@dist;

__DATA__
...