結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー kuroi_13
提出日時 2017-03-27 12:05:38
言語 Perl
(5.40.0)
結果
WA  
実行時間 -
コード長 1,316 bytes
コンパイル時間 127 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 26,624 KB
最終ジャッジ日時 2024-07-06 12:12:43
合計ジャッジ時間 1,812 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.pl syntax OK

ソースコード

diff # 

use strict;
use warnings;

my @tmp = split(' ', <STDIN>);
my %ini = (x => $tmp[0], y => $tmp[1]);
my $n = <STDIN>;

my $wgt = 0;
my @des;
for(1..$n){
  @tmp = split(' ', <STDIN>);
  push @des, {x => $tmp[0], y => $tmp[1], w => $tmp[2]};
  $wgt += $tmp[2];
}

my $diff = 0;
my $t = 0;

my @dp;

my $inf = 999999999;

for my $i (0..(1<<$n)-1){
  for my $j(0..$n-1){
    $dp[$i][$j] = [$inf, 0];
  }
}
for my $i (0..$n-1){
  $diff = abs($des[$i]->{x} - $ini{x}) + abs($des[$i]->{y} - $ini{y});
  $t = $diff * ($wgt + 100)/120 + $des[$i]->{w};
  $dp[1<<$i][$i] = [$t, $wgt - $des[$i]->{w}];
}


my $ni;
my $val = 0;
for my $i (1..(1<<$n)-1){
  for my $j (0..$n-1){
    next if($dp[$i][$j]->[0] == $inf);

    $wgt = $dp[$i][$j]->[1];
    for my $k (0..$n-1){
      next if(($i>>$k) % 2);

      $ni = $i | (1<<$k);
      $diff = abs($des[$k]->{x} - $des[$j]->{x}) + abs($des[$k]->{y} - $des[$j]->{y});
      $t = $diff * ($wgt + 100)/120 + $des[$k]->{w};
      if($dp[$i][$j]->[0] + $t < $dp[$ni][$k]->[0]){
        $dp[$ni][$k] = [$dp[$i][$j]->[0] + $t, $wgt - $des[$k]->{w}];
      }
    }
  }
}

my $ans = $inf;
my $ai = 0;
for(0..$n-1){
  if($dp[(1<<$n)-1][$_][0] < $ans){
    $ans = $dp[(1<<$n)-1][$_][0];
    $ai = $_;
  }
}

$ans += (abs($des[$ai]->{x} - $ini{x}) + abs($des[$ai]->{y} - $ini{y}))*5/6;
print $ans;
0