結果
問題 | No.1 道のショートカット |
ユーザー | chrom_sh |
提出日時 | 2015-01-13 22:50:34 |
言語 | Perl (5.38.2) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,161 bytes |
コンパイル時間 | 130 ms |
コンパイル使用メモリ | 6,216 KB |
実行使用メモリ | 7,256 KB |
最終ジャッジ日時 | 2023-09-22 11:51:33 |
合計ジャッジ時間 | 7,596 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
6,132 KB |
testcase_01 | AC | 15 ms
6,160 KB |
testcase_02 | AC | 15 ms
6,132 KB |
testcase_03 | AC | 15 ms
6,012 KB |
testcase_04 | AC | 15 ms
6,056 KB |
testcase_05 | AC | 15 ms
6,136 KB |
testcase_06 | AC | 15 ms
6,072 KB |
testcase_07 | AC | 15 ms
6,144 KB |
testcase_08 | AC | 84 ms
7,052 KB |
testcase_09 | AC | 21 ms
6,904 KB |
testcase_10 | AC | 143 ms
7,256 KB |
testcase_11 | TLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
コンパイルメッセージ
Main.pl syntax OK
ソースコード
# http://yukicoder.me/problems/17 use strict; use warnings; use 5.010; use Data::Dumper; my $goal = _read_line(); my $money = _read_line(); my $roads = _read_line(); my $map = read_map(); # 前処理終了。 # 解く my $ans = solve($map, $money, $goal); say $ans; sub _read_line { my $line = <STDIN>; chomp($line); return $line; } sub read_map { my $s = [split(/ /, _read_line())]; my $t = [split(/ /, _read_line())]; my $y = [split(/ /, _read_line())]; my $m = [split(/ /, _read_line())]; my $ret = {}; ## これ同じ街間に別経路が存在する場合があるみたい。 ## なので、コストと距離は配列で持つ。 for (my $i = 0 ; $i < @$s ; $i++) { my $start = $s->[$i]; my $dest = $t->[$i]; $ret->{$start} ||= {}; $ret->{$start}->{$dest} ||= []; push @{ $ret->{$start}->{$dest} }, { cost => $y->[$i], dist => $m->[$i], }; } return $ret; } sub solve { my ($map, $money, $goal) = @_; my $cur = [ { pos => 1, cost => 0, dist => 0, } ]; my $res = []; while (my $state = pop(@$cur)) { while (my ($k, $v_array) = each(%{$map->{ $state->{ pos } }})) { for my $v (@$v_array) { my $cost = $v->{ cost } + $state->{ cost }; my $dist = $v->{ dist } + $state->{ dist }; next if ($cost > $money); if ($k == $goal) { push @$res, { cost => $cost, dist => $dist, } } else { push @$cur, { pos => $k, cost => $cost, dist => $dist, }; } } } } $res = [sort {$a->{dist} <=> $b->{dist}} @$res]; return -1 if @$res == 0; return $res->[0]->{dist}; }