Code of agachi
<?

/**
 * Copyright 2003 Agachi Valentin (avalyk2 AT hotmail DOT com)
 */

set_time_limit(120);
error_reporting(E_ALL);


// read input data 

$map_data file('map.txt');
$dest file('dest.txt');

$keys = array();
for (
$ch 'A'$ch 'Z'$ch++)
    
array_push($keys$ch);
array_push($keys'Z');



// generate a 2-dimension matrix

$_keys $keys;
foreach (
$keys as $key1) {
    
$map[$key1] = array();
    foreach (
$_keys as $key2) {
        
$map[$key1][$key2] = array();
    }
    
reset($_keys);
}



// insert input data in the matrix

foreach ($map_data as $map_item) {
    
$map_item_data explode(' 'str_replace(array("\n""\r"), ''$map_item));
    if (
count($map_item_data) == 4) {
        if (
$map_item_data[3] == '1') {
            if (!isset(
$map[$map_item_data[0]][$map_item_data[2]]['len']) || ($map[$map_item_data[0]][$map_item_data[2]]['len'] > $map_item_data[1])) {
                
$map[$map_item_data[0]][$map_item_data[2]]['len'] = $map_item_data[1];
            }
        } else {
            if (!isset(
$map[$map_item_data[0]][$map_item_data[2]]['len']) || ($map[$map_item_data[0]][$map_item_data[2]]['len'] > $map_item_data[1])) {
                
$map[$map_item_data[0]][$map_item_data[2]]['len'] = $map_item_data[1];
            }
            if (!isset(
$map[$map_item_data[2]][$map_item_data[0]]['len']) || ($map[$map_item_data[2]][$map_item_data[0]]['len'] > $map_item_data[1])) {
                
$map[$map_item_data[2]][$map_item_data[0]]['len'] = $map_item_data[1];
            }
        }
    }
}



// Roy-Floyd algorithm to calculate the shortest paths between any 2 points in the matrix

$__keys $_keys $keys;
foreach (
$keys as $k) {
    foreach (
$_keys as $i) {
        foreach (
$__keys as $j) {
            if ((
$i != $j) && isset($map[$i][$k]['len']) && isset($map[$k][$j]['len']) && (!isset($map[$i][$j]['len']) || ($map[$i][$k]['len'] + $map[$k][$j]['len'] < $map[$i][$j]['len']))) {
                
$map[$i][$j]['len'] = $map[$i][$k]['len'] + $map[$k][$j]['len'];
                
$map[$i][$j]['dad'] = $k;
            }
        }
        
reset($__keys);
    }
    
reset($_keys);
}

$dest_points explode(' 'str_replace(array("\n""\r"), ''$dest[0]));
$dest_count count($dest_points);



// a recursise backtracking function to generate all the permutations of the destination points

function blah() {
    global 
$lev$dest_count$dest_points$map$x$v$s$sol$fp$time;
    
$lev++;
    if (
$lev == $dest_count) {
        if (!isset(
$sol['len']) || ($s $sol['len'])) {
            
$sol['len'] = $s;
            
$sol['path'] = $x;
        }
        
$lev--;
        return;
    }
    for (
$i 0$i $dest_count$i++) {
        if (!
$v[$i] && (!isset($sol['len']) || (($lev == 0) || (($lev 0) && ($s $map$dest_points[$x[$lev 1]] ][ $dest_points[$i] ]['len'] < $sol['len']) ))) ) {
            
$x[$lev] = $i$v[$i] = 1
            if (
$lev 0) {
                
$s += $map$dest_points[$x[$lev 1]] ][ $dest_points[$i] ]['len'];
            } else {
                
$s 0;
            }
            
blah();
            
$x[$lev] = -1$v[$i] = 0
            if (
$lev 0) {
                
$s -= $map$dest_points[$x[$lev 1]] ][ $dest_points[$i] ]['len'];
            } else {
                
$s 0;
            }
        }
    }
    
$lev--;
}

$lev = -1;
$x $v = array();
for (
$i 0$i $dest_count$i++) {
    
$x[$i] = -1;
    
$v[$i] = 0;
}
$sol = array();
$s 0;
blah();
//print_r($sol);




// solution output

for ($i 0$i $dest_count$i++) {
    echo 
$dest_points[$sol['path'][$i]].' ';
}
echo 
$sol['len'];
?>






<?
// *************************************************************
// INCLUDE FILE PASTED BELOW FOR DISPLAY ON PHP-EDITORS.COM
// *************************************************************
// FUNCS.MISC.PHP
?><?

///////////////////////////////////////
//                                   //
//          Misc   Functions         //
//     (c) 2001 Agachi Valentin      //
//                                   //
///////////////////////////////////////


/////////////////
//    Debug    //
/////////////////

function d_array_as_string (&$array$s ""$column 0) {
    
$str "<span style=\"color:#009900\">Array $s </span>(<br />\n";
    while(list(
$var$val) = each($array)) {
        
$str .= "<span style=\"color:white\">";
        for (
$i 0$i $column+1$i++){
            
$str .= "===";
        }
        
$str .= "</span>";
        
$str .= '[<span style="color:#3399CC">'.$var.'</span>] --> ';
        
$str .= d_wr2($val$var$column 1)."<br />\n";
    }
    
$str .= "<span style=\"color:white\">";
    for (
$i 0$i $column$i++){
        
$str .= "=====";
    }
    
$str .= "</span>)";
    
reset($array);
    return 
$str;
}

function 
d_object_as_string (&$object$s ""$column 0) {
    if (
trim(get_class($object)) == "") {
        return 
"$object";
    }
    else {
        
$str "<span style=\"color:#009900\">Object ".get_class($object)." </span>(<br />\n";
        
$vars get_object_vars($object);
        while (list(
$var$val) = each($vars)) {
            
$str .= "<span style=\"color:white\">";
            for (
$i 0$i $column+1$i++){
                
$str .= "=====";
            }
            
$str .= "</span>";
            
$str .= '[<span style="color:#3399CC">'.$var.'</span>] --> ';
            
$str .= d_wr2($val""$column+1)."<br />\n";
        }
        
$vars get_class_methods(get_class($object));
        while (list(
$id$val) = each($vars)) {
            
$str .= "<span style=\"color:white\">";
            for (
$i 0$i $column+1$i++){
                
$str .= "=====";
            }
            
$str .= "</span><span style=\"color:#FF0000\">";
            
$str .= $val."</span>()<br />\n";
        }
        
$str .= "<span style=\"color:white\">";
        for (
$i 0$i $column-1$i++){
            
$str .= "=====";
        }
        
$str .= "</span>)";
        return 
$str;
    }
}

function 
d_wr2(&$thing$s ""$column 0) {
    if (
is_object($thing)) {
        return 
d_object_as_string($thing$s$column);
    }
    elseif (
is_array($thing)) {
        return 
d_array_as_string($thing$s$column);
    }
    elseif (
is_double($thing)) {
        return 
"Double(<span style=\"color:#0000CC\">".$thing."</span>)";
    }
    elseif (
is_long($thing)) {
        return 
"Long(<span style=\"color:#0000CC\">".$thing."</span>)";
    }
    elseif (
is_string($thing)) {
        return 
"String(<span style=\"color:#FF00CC\">".htmlentities($thing)."</span>)";
    }
    elseif (
is_bool($thing)) {
        if (
$thing)
            return 
"Bool(<span style=\"color:#CC0000\">True</span>)";
        else return 
"Bool(<span style=\"color:#CC0000\">False</span>)";
    }
    else {
        return 
"Unknown(<span style=\"color:#CC0000\">".$thing."</span>)";
    }
}

function 
wr(&$thing$s "") {
    echo 
"<span style=\"font-family:Tahoma; font-size:8pt; font-weight:bold\">";
    echo 
d_wr2($thing$s);
    echo 
"</span>";
}

//////////////////
//    Timer     //
//////////////////

function d_timer_start ($name 'default') {
    global 
$d_timer_start_times;
    
$d_timer_start_times[$name] = explode(' 'microtime());
}

function 
d_timer_stop ($name 'default') {
    global 
$d_timer_stop_times;
    
$d_timer_stop_times[$name] = explode(' 'microtime());
}

function 
d_timer_value ($name 'default') {
    global 
$d_timer_start_times$d_timer_stop_times;
    if (!isset(
$d_timer_start_times[$name]))
        return 
0;
    if (!isset(
$d_timer_stop_times[$name]))
        
$stop_time explode(' 'microtime());
    else 
$stop_time $d_timer_stop_times[$name];
    
$current $stop_time[1] - $d_timer_start_times[$name][1];
    
$current += $stop_time[0] - $d_timer_start_times[$name][0];
    return 
$current;
}

/////////////////
//     Misc    //
/////////////////

function post_check()
{
    
$accept false;
    
$hoststr "http://".$_SERVER['HTTP_HOST'].$_SERVER['PHP_SELF'];
    if(
substr($_SERVER['HTTP_REFERER'], 0strlen($hoststr)) == $hoststr$accept true;
    
$hoststr "https://".$_SERVER['HTTP_HOST'].$_SERVER['PHP_SELF'];
    if(
substr($_SERVER['HTTP_REFERER'], 0strlen($hoststr)) == $hoststr$accept true;
    return 
$accept;
}

function 
show_img($img$style "")
{
    if (
$style$style .= ' ';
    
$size = @GetImageSize($img);
    echo 
'<img src="'.$img.'" '.$size[3].' border="0" '.$style.'/>';
}

function 
str_strip(&$s$strip true$slash true$trim false)
{
    if (
$strip$s strip_tags($s);
    if (
$slash$s addslashes($s);
    if (
$trim$s trim($s);
}

function 
array_slash(&$array$strip true$slash true$trim false)
{
    
$keys array_keys($array);
    for(
$i 0$i count($keys); $i++)
        
str_strip($array[$keys[$i]], $strip$slash$trim);
}

function 
array_format(&$array$func)
{
    
$keys array_keys($array);
    for(
$i 0$i count($keys); $i++)
        
$array[$keys[$i]] = $func($array[$keys[$i]]);
}

function 
strip_http($str)
{
    
$t preg_replace("~^(http|https):\/\/(.*)\/?$~""\\2"$str);
    if (
$t{strlen($t) - 1} == '/')
        return 
substr($t0strlen($t) - 1);
    else return 
$t;
}

function 
roman(&$n)
{
    
$romans = array(=> 'I'=> 'II'=> 'III'=> 'IV'=> 'V'=> 'VI'=> 'VII'=> 'VIII'=> 'IX'10 => 'X'11 => 'XI'12 => 'XII');
    return 
$romans[$n];
}

function 
str_cut($s$limit 16$suffix '...') {
    return (
strlen($s) <= $limit) ? $s substr($s0$limit).$suffix;
}

?>


Back to results


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