結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー 綾地寧々
提出日時 2015-07-15 10:51:53
言語 PHP
(843.2)
結果
AC  
実行時間 242 ms / 5,000 ms
コード長 3,166 bytes
コンパイル時間 2,411 ms
コンパイル使用メモリ 30,996 KB
実行使用メモリ 31,216 KB
最終ジャッジ日時 2024-10-15 01:25:40
合計ジャッジ時間 6,131 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
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