結果

問題 No.17 2つの地点に泊まりたい
ユーザー 綾地寧々綾地寧々
提出日時 2015-07-15 10:51:53
言語 PHP
(8.3.4)
結果
AC  
実行時間 245 ms / 5,000 ms
コード長 3,166 bytes
コンパイル時間 2,077 ms
コンパイル使用メモリ 32,276 KB
実行使用メモリ 32,528 KB
最終ジャッジ日時 2024-04-23 02:06:18
合計ジャッジ時間 5,700 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
32,400 KB
testcase_01 AC 38 ms
32,272 KB
testcase_02 AC 42 ms
32,400 KB
testcase_03 AC 172 ms
32,404 KB
testcase_04 AC 55 ms
32,272 KB
testcase_05 AC 156 ms
32,400 KB
testcase_06 AC 109 ms
32,400 KB
testcase_07 AC 91 ms
32,400 KB
testcase_08 AC 241 ms
32,400 KB
testcase_09 AC 233 ms
32,528 KB
testcase_10 AC 200 ms
32,400 KB
testcase_11 AC 245 ms
32,400 KB
testcase_12 AC 41 ms
32,528 KB
testcase_13 AC 37 ms
32,144 KB
testcase_14 AC 39 ms
32,404 KB
testcase_15 AC 37 ms
32,276 KB
testcase_16 AC 37 ms
32,400 KB
testcase_17 AC 50 ms
32,404 KB
testcase_18 AC 129 ms
32,528 KB
testcase_19 AC 106 ms
32,400 KB
testcase_20 AC 45 ms
32,400 KB
testcase_21 AC 42 ms
32,144 KB
testcase_22 AC 151 ms
32,400 KB
testcase_23 AC 154 ms
32,404 KB
testcase_24 AC 185 ms
32,144 KB
testcase_25 AC 40 ms
32,340 KB
testcase_26 AC 214 ms
32,400 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