Code of torsten
<?php
$iResultLength 
= -1;                    // result length
$arrResultPath = array();                // result path

$arrNodes $arrNodeToWay $arrNodeFromWay = array();
foreach(
file("map.txt") as $sLine){
    
$arrLine explode(" ",strtoupper(trim($sLine)));
    if((
sizeof($arrLine)==4) && $arrLine[0]!=$arrLine[2]){    // ignore empty/damaged lines and routes that start and end at the same point
        
if(!isset($arrNodes[$arrLine[0]][$arrLine[2]]) || $arrNodes[$arrLine[0]][$arrLine[2]]>$arrLine[1]){
            
$arrNodes[$arrLine[0]][$arrLine[2]] = $arrLine[1];
            if(!isset(
$arrNodeToWay[$arrLine[2]]) || $arrLine[1]<$arrNodeToWay[$arrLine[2]]){
                
$arrNodeToWay[$arrLine[2]] = $arrLine[1];
            }
            if(!isset(
$arrNodeFromWay[$arrLine[0]]) || $arrLine[1]<$arrNodeFromWay[$arrLine[0]]){
                
$arrNodeFromWay[$arrLine[0]] = $arrLine[1];
            }
        }
        if(
$arrLine[3]==2){                                    // bidirectional
            
if(!isset($arrNodes[$arrLine[2]][$arrLine[0]]) || $arrNodes[$arrLine[2]][$arrLine[0]]>$arrLine[1]){
                
$arrNodes[$arrLine[2]][$arrLine[0]] = $arrLine[1];
                if(!isset(
$arrNodeToWay[$arrLine[0]]) || $arrLine[1]<$arrNodeToWay[$arrLine[0]]){
                    
$arrNodeToWay[$arrLine[0]] = $arrLine[1];
                }
                if(!isset(
$arrNodeFromWay[$arrLine[2]]) || $arrLine[1]<$arrNodeFromWay[$arrLine[2]]){
                    
$arrNodeFromWay[$arrLine[2]] = $arrLine[1];
                }
            }
        }
    }
}

reset($arrNodes);
while(list(
$sKey,) = each($arrNodes)){
    
asort($arrNodes[$sKey],SORT_NUMERIC);
}

$arrDelivery = array();
foreach(
file("dest.txt") as $sLine){
    if(
$sLine trim($sLine)) $arrDelivery explode(" ",strtoupper($sLine));
}
$sDelivery implode("",$arrDelivery);
usort($arrDelivery,"cmpDeliveryNode");
$arrCountDelivery array_count_values($arrDelivery);

foreach(
$arrDelivery as $sStartPoint){
    if(isset(
$GLOBALS["arrNodes"][$sStartPoint])){
        
processNode(array($sStartPoint),0);
    }
}
echo 
implode(" ",array_intersect($arrResultPath,$arrDelivery))." ".$iResultLength;

function 
processNode($arrPath,$iLength){

    global     
$arrNodes,
            
$arrCountDelivery,
            
$arrDelivery,
            
$sDelivery,
            
$arrNodeFromWay,
            
$arrNodeToWay,
            
$iResultLength,
            
$arrResultPath;

    
$sPath implode("",$arrPath);
    
$iStartElement end($arrPath);
    
$iLastElement prev($arrPath);
    
$arrCountPath array_count_values($arrPath);

    
$arrFirst $arrSecond $arrThird = array();
    foreach(
$arrNodes[$iStartElement] as $sDest=>$iLengthDest){

        if(!isset(
$arrCountPath[$sDest])){
            if(isset(
$arrCountDelivery[$sDest])){
                
$arrFirst[$sDest] = $iLengthDest;
            }
            else{
                
$arrSecond[$sDest] = $iLengthDest;
            }
        }
        else{
            if(
$iLastElement !== $sDest || ($arrCountPath[$iStartElement]<&& isset($arrCountDelivery[$iStartElement]))){
                
$arrThird[$sDest] = $iLengthDest;
            }
        }
    }

    
$arrTodo array_diff($arrDelivery,$arrPath);
    foreach(
$arrFirst+$arrSecond+$arrThird as $sDest=>$iLengthDest){

        
$iEstimatedMinLength $iTmpLength $iLength+$iLengthDest;

        
$arrPathTmp $arrPath;
        
$arrPathTmp[] = $sDest;
        
$arrTodoTmp $arrTodo;
        if((
$iDestKey array_search($sDest,$arrTodoTmp))!==FALSE){
            unset(
$arrTodoTmp[$iDestKey]);
        }
        if(
$arrTodoTmp && !array_intersect($arrTodoTmp,array_keys($arrNodes[$sDest]))){
            
$iEstimatedMinLength += $arrNodeFromWay[$sDest];
        }
        foreach(
$arrTodoTmp as $sDeliveryElement){
            
$iEstimatedMinLength += $arrNodeToWay[$sDeliveryElement];
        }
        if(
$iResultLength>=&& $iEstimatedMinLength>=$iResultLength){
            continue;
        }
        if(!
$arrTodoTmp){
            
$iResultLength $iTmpLength;
            
$arrResultPath $arrPathTmp;
#            echo implode("",$arrPathTmp).": $iTmpLength\n";
            
break;
        }

        if((
$iPos strrpos($sPath,$sDest))!==FALSE){
            
$sSearch substr($sPath.$sDest,$iPos+1);
            
$sSearchLength strlen($sSearch);
            if((
strcspn($sSearch,$sDelivery)===$sSearchLength-1)
                 || 
substr($sPath,($sSearchLength*-2)+1,$sSearchLength)===$sSearch
                 
|| strpos($sPath,$sDest.$sSearch)!==FALSE){
                continue;
            }
        }
        if(isset(
$arrNodes[$sDest])){
            
processNode($arrPathTmp,$iTmpLength);
        }
    }
}

function 
cmpDeliveryNode($a,$b){
    global 
$arrNodes;
    if(isset(
$arrNodes[$a]) && isset($arrNodes[$b])){
        
$aSize sizeof($arrNodes[$a]);
        
$bSize sizeof($arrNodes[$b]);
        if(
$aSize==$bSize){
            if(
$aSize==1){
                
$aLength end($arrNodes[$a]);
                
$bLength end($arrNodes[$b]);
                if(
$aLength==$bLength) return 0;
                else return(
$aLength>$bLength)?-1:1;
            }
            else return 
0;
        }
        else return(
$aSize<$bSize)?-1:1;
    }
    else return 
0;
}
?>


Back to results


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