結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー 綾地寧々
提出日時 2015-07-07 22:48:29
言語 PHP
(843.2)
結果
WA  
実行時間 -
コード長 2,870 bytes
コンパイル時間 2,312 ms
コンパイル使用メモリ 31,760 KB
実行使用メモリ 32,660 KB
最終ジャッジ日時 2024-07-08 01:32:59
合計ジャッジ時間 2,955 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php
$point = trim(fgets(STDIN));
$stay_cost = array();
for ( $i=0; $i<$point; $i++ ) {
	$stay_cost[] = strval(trim(fgets(STDIN)));
}
$m = trim(fgets(STDIN));
$input_move_cost = array(array(), array());
$move_cost = array(array(), array());
for ( $i=0; $i<$m; $i++ ) {
	list($dep, $arr, $mov) = explode(" ", trim(fgets(STDIN)));
	if ( $dep < $arr ) {
		$input_move_cost[$dep][$arr] = $mov;
	}
	else {
		$input_move_cost[$arr][$dep] = $mov;
	}
}
// 任意地点から任意地点までの最小移動コストを計算する
calc_move_cost();

$minimum = FALSE;
// 滞在地点を2つ選び、移動コスト+滞在コストが最小となるパターンを探す
for ( $i=1; $i<$point-1; $i++ ) {
	for ( $j=1; $j<$point-1; $j++ ) {
		// 1回目と2回目の滞在地点が同じのは許されないです
		if ( $i == $j ) {
			continue;
		}
		$minimum = my_min(get_move_cost(0,$i) + get_move_cost($i, $j) + get_move_cost($j, $point-1) + $stay_cost[$i] + $stay_cost[$j], $minimum);
	}
}

echo $minimum .PHP_EOL;

// 全パターンの最小移動コストを計算します。
function calc_move_cost (  ) {
	global $point, $move_cost;
	for ( $dep=0; $dep<$point; $dep++ ) {
		for ( $arr=$dep; $arr<$point; $arr++ ) {
			move_point($dep, $arr);
		}
	}
}

// $start から $end まで移動するコストを探索し返却します。
function move_point ( $start, $end ) {
	global $m, $input_move_cost, $move_cost;
	// 移動元と移動先が一緒なら
	if ( $start == $end ) {
		return 0;
	}
	// 移動先より移動元のほうが後ろなら、ひっくり返す
	if ( $start > $end ) {
		$t = $start;
		$start = $end;
		$end = $t;
	}
	// すでに計算済なら・もしくはループ検出
	if ( ($return = get_move_cost($start, $end)) !== FALSE ) {
		return $return;
	}
	// 探索開始
	$minimum = FALSE;
	$move_cost[$start][$end] = FALSE;
	foreach ( $input_move_cost[$start] as $moveto => $cost ) {
		$return = move_point($moveto, $end);
		$minimum = my_min($return + intval($cost), $minimum);
	}
	$move_cost[$start][$end] = $minimum;
	return $move_cost[$start][$end];
}

// $start から $end まで移動するコストを返却します
function get_move_cost ( $start, $end ) {
	global $move_cost;
	// 移動元と移動先が一緒なら
	if ( $start == $end ) {
		return 0;
	}
	// 移動先より移動元のほうが後ろなら、ひっくり返す
	if ( $start > $end ) {
		$t = $start;
		$start = $end;
		$end = $t;
	}
	// すでに計算済ならそれを返却
	if ( isset($move_cost[$start][$end]) ) {
		return $move_cost[$start][$end];
	}
	// 未計算なら FALSE 、もしくはそもそも到達できない場合
	else {
		return FALSE;
	}
}

function my_min ( $a, $b ) {
	if ( ($a === FALSE) && ($b === FALSE) ) {
		return FALSE;
	}
	if ( $a === FALSE ) {
		return $b;
	}
	if ( $b === FALSE ) {
		return $a;
	}
	return min($a, $b);
}
0