結果

問題 No.17 2つの地点に泊まりたい
ユーザー 綾地寧々綾地寧々
提出日時 2015-07-15 10:51:53
言語 PHP
(7.2.24)
結果
AC  
実行時間 273 ms / 5,000 ms
コード長 3,166 bytes
コンパイル時間 570 ms
コンパイル使用メモリ 18,728 KB
実行使用メモリ 18,996 KB
最終ジャッジ日時 2023-08-05 03:37:41
合計ジャッジ時間 4,465 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
18,968 KB
testcase_01 AC 15 ms
18,936 KB
testcase_02 AC 21 ms
18,976 KB
testcase_03 AC 189 ms
18,856 KB
testcase_04 AC 37 ms
18,948 KB
testcase_05 AC 161 ms
18,996 KB
testcase_06 AC 100 ms
18,884 KB
testcase_07 AC 74 ms
18,924 KB
testcase_08 AC 259 ms
18,972 KB
testcase_09 AC 261 ms
18,904 KB
testcase_10 AC 220 ms
18,768 KB
testcase_11 AC 273 ms
18,952 KB
testcase_12 AC 15 ms
18,964 KB
testcase_13 AC 15 ms
18,768 KB
testcase_14 AC 15 ms
18,976 KB
testcase_15 AC 15 ms
18,956 KB
testcase_16 AC 16 ms
18,896 KB
testcase_17 AC 30 ms
18,932 KB
testcase_18 AC 135 ms
18,888 KB
testcase_19 AC 104 ms
18,984 KB
testcase_20 AC 26 ms
18,960 KB
testcase_21 AC 19 ms
18,996 KB
testcase_22 AC 158 ms
18,832 KB
testcase_23 AC 162 ms
18,908 KB
testcase_24 AC 205 ms
18,908 KB
testcase_25 AC 20 ms
18,772 KB
testcase_26 AC 247 ms
18,772 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php
$start = microtime(TRUE);
$point = trim(fgets(STDIN));
$stay_cost = array();
for ( $i=0; $i<$point; $i++ ) {
	$stay_cost[] = strval(trim(fgets(STDIN)));
}
$m = trim(fgets(STDIN));
$mc = new MoveCost();
for ( $i=0; $i<$m; $i++ ) {
	list($dep, $arr, $mov) = explode(" ", trim(fgets(STDIN)));
	$mc->set_cost($dep, $arr, $mov);
}
// 任意地点から任意地点までの最小移動コストを計算する
// ワーシャルフロイド法っていうらしいですよ。
for ( $k=0; $k<$point; $k++ ) {
	for ( $i=0; $i<$point; $i++ ) {
		for ( $j=0; $j<$point; $j++ ) {
			$mc->set_cost($i,$j,my_min($mc->get_cost($i,$j), ($mc->is_set_cost($i,$k) && $mc->is_set_cost($k,$j)) ? $mc->get_cost($i,$k)+$mc->get_cost($k,$j) : FALSE));
		}
	}
}

$minimum = FALSE;
// 滞在地点を2つ選び、移動コスト+滞在コストが最小となるパターンを探す
for ( $i=1; $i<$point-1; $i++ ) {
	for ( $j=1; $j<$point-1; $j++ ) {
		// 1回目と2回目の滞在地点が同じのは許されないです
		if ( $i == $j ) {
			continue;
		}
		// 到達できない地点へ移動しようとしたときは処理スキップ
		if ( !($mc->is_set_cost(0,$i)) || !($mc->is_set_cost($i,$j)) || !($mc->is_set_cost($j,$point-1)) ) {
			continue;
		}
		$minimum = my_min($mc->get_cost(0,$i) + $mc->get_cost($i, $j) + $mc->get_cost($j, $point-1) + $stay_cost[$i] + $stay_cost[$j], $minimum);
	}
}

echo $minimum .PHP_EOL;

// 最小移動コストの記憶用クラス。
class MoveCost {
	private $_move_cost = array(array(), array());
	function __construct () {

	}
	function __destruct () {

	}
	// $start から $end までの移動コストを返却します。
	public function get_cost ($start, $end) {
		if ( $start == $end ) {
			return 0;
		}
		swap($start, $end);
		return ($this->is_set_cost($start, $end)) ? $this->_move_cost[$start][$end] : FALSE;
	}

	// $start から $end までの移動コストを設定します。
	public function set_cost ($start, $end, $cost) {
		if ( $start == $end ) {
			return 0;
		}
		swap($start, $end);
		$this->_move_cost[$start][$end] = $cost;
		return $this->_move_cost[$start][$end];
	}

	// $start から $end までの移動コストが設定済か返却します。
	public function is_set_cost ($start, $end) {
		swap($start, $end);
		if ( $start == $end ) {
			return TRUE;
		}
		if ( isset($this->_move_cost[$start][$end]) ) {
			return ($this->_move_cost[$start][$end] === FALSE) ? FALSE : $this->_move_cost[$start][$end];
		}
		else {
			return FALSE;
		}
	}

	public function debug_print_move_cost () {
		foreach ( $this->_move_cost as $start => $toarray ) {
			foreach ( $toarray as $end => $cost ) {
				fprintf(STDERR, "[{$start}][{$end}] => {$cost}\n");
			}
		}
	}

}

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);
}

// $a と $b 2つの値について、$a が必ず小さくなるようにします。
function swap (&$a, &$b) {
	if ( $a > $b ) {
		$t = $a;
		$a = $b;
		$b = $t;
	}
}
$exec = microtime(TRUE) - $start;
fprintf(STDERR, "EXEC: {$exec}\n");
0