forked from manwar/perlweeklychallenge-club
/
ch-2.pl
57 lines (46 loc) · 1.41 KB
/
ch-2.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#!/opt/perl/bin/perl
use 5.032;
use strict;
use warnings;
no warnings 'syntax';
use experimental 'signatures';
use experimental 'lexical_subs';
#
# See ../README.md
#
#
# Run as: perl ch-2.pl < input-file
#
#
# Find the shorted path from '$from' to '$to', using all entries
# in '$matrix', except the ones in '$exclude'.
#
sub shortest_path ($matrix, $from, $to, $exclude) {
if (1 + keys %$exclude == @$matrix) {
#
# We have excluded everything, except the destination.
# This makes it the only, and hence, shortest path.
#
return ($$matrix [$from] [$to], [$to]);
}
#
# Else, try each node other than $from, $to, and what's in $exclude,
# as the first step. Then recurse, and return the shortest.
#
my $shortest = ~0;
my @shortest_path;
my %new_exclude = (%$exclude, $from => 1);
foreach my $next (0 .. @$matrix - 1) {
next if $next == $from || $next == $to || $$exclude {$next};
my ($length, $path) = shortest_path ($matrix, $next, $to,
\%new_exclude);
if ($shortest > $length + $$matrix [$from] [$next]) {
$shortest = $length + $$matrix [$from] [$next];
@shortest_path = ($next, @$path);
}
}
return $shortest, \@shortest_path;
}
my @matrix = map {[split]} <>;
my ($length, $path) = shortest_path \@matrix, 0, 0, {};
say "$length\n0 @$path";