#! perl -slw
use strict;
use threads;
use threads::shared;

my @dists = map[ split ' ' ], <DATA>;

sub totalEm {
    my $aref = shift;
    my $total = 0;
    $total += $dists[ $aref->[ $_ - 1] ][ $aref->[ $_ ] ] for 1 .. $#{ $aref };
    return $total;
}

my $best :shared = 1e9;
sub rPath {
    my( $soFar, $path, $toAdd, $tid ) = @_;
    return if $soFar > $best;

    unless( @$toAdd ) {
        $soFar += $dists[ $path->[ -1 ] ][ 23 ];
        if( $soFar < $best ) {
            printf "[%2u] %u: @$path 23\n", $tid, $soFar,;
            $best = $soFar;
        }
        return;
    }

    my $last = $dists[ $path->[-1] ];
    my @ordered = sort { $last->[$a] <=> $last->[$b] } @$toAdd;

    for( 1 .. @ordered ) {
        my $next = shift @ordered;
        rPath( $soFar + $dists[ $path->[-1] ][ $next ], [ @$path, $next ], \@ordered, $tid );
        push @ordered, $next;
    }
}

our $T //= 4;
my $running :shared = 0;
for( 1 .. 22 ) {
    {lock $running; ++$running }
    async{
        my $tid = threads->tid;
        rPath( $dists[ 0 ][ $_ ], [ 0, $_ ], [ 1..$_-1, $_+1 .. 22 ], $tid );
        { lock $running; --$running; }
    }->detach;
    sleep 1 while $running > $T-1
}

sleep 1 while $running;

__DATA__