Code of barry
<?php
/****************************************************************
Contest B4
-----------------------------------------------------------------
Author : Barry A Andrew
Copyright : © B A Andrew 2003
email : barryaandrew@aol.com
Date : 22 July 2003
****************************************************************/
class mapper {
var $links = array();
var $dests = array();
var $nodes = array();
var $nodeLinks = array();
function mapper($mapfile, $destfile) {
$this->getMapFile($mapfile);
$this->getDestFile($destfile);
return;
}
function __construct($mapfile, $destfile) {
$this->mapper($mapfile, $destfile);
}
function addLink($from,$to,$dist) {
if (!isset($this->links[$from][$to]) || ($this->links[$from][$to] > $dist)) {
$this->links[$from][$to] = $dist;
}
return;
}
function getMapFile($fname) {
$map = file($fname);
$ncount = 0;
foreach ($map as $link) {
list($from,$dist,$to,$type) = explode(' ', trim($link));
$this->addLink($from,$to,$dist);
if ($type==2) $this->addLink($to,$from,$dist);
elseif ($type==1) $this->addLink($to,$from,999);
if (!$this->nodes[$from]) $this->nodes[$from] = $ncount++;
if (!$this->nodes[$to]) $this->nodes[$to] = $ncount++;
}
$this->nodes = array_flip($this->nodes);
sort($this->nodes);
ksort($this->links);
foreach ($this->nodes as $adest) {
foreach ($this->nodes as $bdest) {
if ($adest != $bdest) {
$routes = array(path=>'', dist=>999);
$this->calcPath($adest,$bdest,$routes,0,$adest);
$this->nodeLinks[$adest][$bdest]['d'] = $routes['dist'];
$a = explode(' ', $routes['path']);
$this->nodeLinks[$adest][$bdest]['p'] = $a;
}
}
}
return;
}
function getDestFile($fname) {
$dest = file($fname);
$this->dests = explode(' ', trim($dest[0]));
return;
}
function calcPath($adest, $bdest, &$routes, $dist=0, $path='') {
if ($this->links[$adest])
foreach ($this->links[$adest] as $s => $d) {
if (strlen($path) > 26) break;
if (strpos($path,$s)!==false) continue;
if ($s==$bdest) {
if ($dist + $d < $routes['dist']) {
$routes['path'] = $path.' '.$s;
$routes['dist'] = $dist + $d;
}
}
else {
$this->calcPath($s,$bdest,$routes,$dist+$d,$path.' '.$s);
}
}
}
function shortPath($x,$p, $d, $lastp, &$paths) {
if (count($x)==1) {
$nod = $x[0];
$dst = $d + $this->nodeLinks[$lastp][$nod]['d'];
if ($dst < $paths['dist']) {
$paths['path'] = $p.' '.$nod;
$paths['dist'] = $dst;
}
return;
}
else
foreach ($x as $start) {
foreach ($x as $end) {
if ($end==$start) continue;
$a = $this->nodeLinks[$start][$end]['p'];
$b = array_values(array_diff($x, $a));
if (count($b)==0) {
$dst = $d + $this->nodeLinks[$lastp][$start]['d'] + $this->nodeLinks[$start][$end]['d'];
if ($dst < $paths['dist']) {
$paths['path'] = $p.' '.join(' ',$a);
$paths['dist'] = $dst;
}
return;
}
else {
$c = count($a);
$this->shortPath($b,$p.' '.join(' ',$a),
$d + $this->nodeLinks[$lastp][$start]['d'] + $this->nodeLinks[$start][$end]['d'],
$a[$c-1], $paths);
}
}
}
}
function delivery_path() {
$paths = array(path=>'', dist=>999);
$this->shortPath($this->dests,'',0,'',$paths);
$a = explode(' ', $paths['path']);
$a = array_intersect($a,$this->dests);
echo join('',$a) . ' ' . $paths['dist'];
return;
}
}
function getmicrotime(){
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}
//$timea = getmicrotime();
$map = new mapper('map.txt','dest.txt');
$map->delivery_path();
//$timeb = getmicrotime();
//$tottime = $timeb - $timea;
?>
Back to results
|
|