fork download 
  1. #!/usr/bin/perl
  2. # 3/316 by Dijkstra shortest path , w/o using priority queue
  3. @s = qw{13457689768914512071934123457
  4. 	G4578901258901212890361125312
  5. 	37890423076834712378998725463
  6. 	16890102569615902061456259893
  7. 	34582934765923812893461515232
  8. 	57896123896741378915691551697
  9. 	89013897456123457162501835479
  10. 	21389046013845610034623405686
  11. 	8902346203948612341356362342S};
  12.  
  13. $nj = @s;
  14. $ni = length $s[0];
  15. @t = map{[split'']} @s;
  16.  
  17. for $j (0..$nj-1) {
  18.   for $i (0..$ni-1) {
  19.     $c = $t[$j][$i];
  20.     $node{"$j $i"} = ~0; # Huge int
  21.     if ($c =~ /[SG]/) {
  22.       ${$c} = "$j $i";
  23.       $node{"$j $i"} = 0 if $c eq 'S';
  24.     }
  25.     for ([-1,0],[0,-1],[1,0],[0,1]) {
  26.       $ii = $i + $$_[0];
  27.       $jj = $j + $$_[1];
  28.       if (0 <= $ii and $ii < $ni and
  29. 	  0 <= $jj and $jj < $nj) {
  30. 	$edge{"$jj $ii"}{"$j $i"} = $c;
  31.       }
  32.     }
  33.   }
  34. }
  35.  
  36. use List::Util min;
  37. while (@ss = sort{$node{$a} <=> $node{$b}} keys %node) {
  38.   $s = @ss[0];
  39.   $c = $node{$s};
  40.   $path{$s} = $c;
  41.   delete $node{$s};
  42.   for $d (keys %{$edge{$s}}) {
  43.     next unless exists $node{$d};
  44.     $node{$d} = min($node{$d}, $c + $edge{$s}{$d});
  45.   }
  46. }
  47. print "$S => $G: $path{$G}\n";
Success #stdin #stdout 0.01s 20120KB
comments (?)
stdin 
Standard input is empty
stdout 
8 28 => 1 0: 100
https://ideone.com/XcsBQe
language:
Perl (perl 5.28.1)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!