2015/17.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4 use strict;
   5
   6 $; = ',';
   7
   8 my %route;
   9 my %cities;
  10 while (<>) {
  11         my ($src, $dst, $len) = /^(\w+) to (\w+) = (\d+)/;
  12         $cities{$src} = $cities{$dst} = 1;
  13         $route{$src,$dst} = $len;
  14         $route{$dst,$src} = $len;
  15 }
  16
  17
  18 my $min_dist;
  19 sub do_perm {
  20         my ($path, $dist, $rest) = @_;
  21
  22         if (!@$rest) {
  23                 $min_dist = $dist if !$min_dist || $dist < $min_dist;
  24                 say "new min $min_dist";
  25                 return;
  26         }
  27         for my $i (0 .. $#$rest) {
  28                 my @nrest = @$rest;
  29                 my ($next) = splice (@nrest, $i, 1);
  30                 my @npath = (@$path, $next);
  31                 my $ndist = $dist;
  32                 if (@$path) {
  33                         my $prev = $path->[-1];
  34                         $ndist += $route{$prev,$next};
  35                 }
  36                 # say join(',', @npath), " $ndist";
  37                 do_perm(\@npath, $ndist, \@nrest);
  38         }
  39 }
  40
  41 do_perm([], 0, [ keys %cities ]);
  42 say $min_dist;
  43