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.0115 sec