U E D R , A S I H C RSS

From Dusk Till Dawn/변형진

2 , 트해... . :)

~php
<?
new Vladimir();
class Vladimir
{
	var $train;
	var $days;
	function __construct()
	{
		$ln = explode("\n", "2\n3\nUlm Muenchen 17 2\nUlm Muenchen 19 12\nUlm Muenchen 5 2\nUlm Muenchen\n11\nLugoj Sibiu 12 6\nLugoj Sibiu 18 6\nLugoj Sibiu 24 5\nLugoj Medias 22 8\nLugoj Medias 18 3\nLugoj Reghin 17 4\nSibiu Reghin 19 6\nSibiu Medias 20 3\nReghin Medias 20 4\nReghin Bacau 24 6\nMedias Bacau 4 6\nLugoj Bacau");
		for($n=0,$k=1; $n<$ln[0]; $n++,$k+=$ln[$k]+2)
		{
			$this->train = array();
			$this->days = 0;
			for($i=0; $i<$ln[$k]; $i++)
			{
				list($from, $to, $start, $end) = explode(" ", trim($ln[$k+$i+1]));
				if(($start<18&&$start>6)||($end<18&&$end>6)||($start<=6&&$start>=$end)||($end>=18&&$end<=$start)) continue;
				$this->train[$from][] = array("to"=>$to, "start"=>($start+6)%24, "end"=>($end+6)%24);
			}
			list($from, $to) = explode(" ", trim($ln[$k+$i+1]));
			$this->track($from, $to);
			echo "Test Case ".($n+1).".<br>";
			if($this->days) echo "Vladimir needs $this->days litre(s) of blood.<br>";
			else echo "There is no route Vladimir can take.<br>";
		}
	}
	function track($from, $to, $start=0, $days=1, $city=array())
	{
		if($city[$from]) return 0;
		$city[$from] = true; $today = $tomorrow = array();
		for($i=0; $this->train[$from][$i]; $i++)
		{
			$next = $this->train[$from][$i][to];
			if($city[$next]) continue;
			if($this->train[$from][$i][start]>=$start)
			{
				if($next==$to)
				{
					if($this->days>$days||!$this->days) $this->days = $days;
					return $days;
				}
				$today[$next] = min(($today[$next])?$today[$next]:0, $this->train[$from][$i][end]-12);
			}
			else $tomorrow[$next] = min(($tomorrow[$next])?$tomorrow[$next]:0, $this->train[$from][$i][end]-12);
		}
		foreach($today as $next => $end) $this->track($next, $to, $end+12, $days, $city);
		foreach($tomorrow as $next => $end)
		{
			if($next==$to)
			{
				if($this->days>$days+1||!$this->days) $this->days = $days+1;
				return $days+1;
			}
			if($today[$next]) continue;
			$this->track($next, $to, $end+12, $days+1, $city);
		}
	}
}
?>
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:17
Processing time 0.0139 sec