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 
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


© Copyright 2003-2014 www.php-editors.com. The ultimate PHP Editor and PHP IDE site.