Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
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]<2 && 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>=0 && $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
|
|
|
