Code of siavash
<?
$map = fopen('map.txt','r');
$i=0;
while(!feof($map))
{
$temp = explode(' ', trim(fgets($map, 40960)));
add_to_map($temp[0],$temp[2],$temp[1]);
if ($temp[3] == 2)
{
add_to_map($temp[2],$temp[0],$temp[1]);
}
}
fclose($map);
$map_dist = array();
for ( $i = 0; isset($map_input[$i]['dist']); $i++)
{
calc_dist($map_input[$i]['from'], $i, $map_input[$i]['from']);
}
/*reset($map_dist);
while ( list($add,$dista) = @each($map_dist) )
{
print("<br> $add | $dista");
}*/
$dest = fopen('dest.txt', 'r');
$where = explode(' ', trim(fgets($dest, 40960)));
fclose($dest);
$nodes_len = 2 * count($where) - 1;
$queue = array();
for ( $i = 0; isset($where[$i]); $i++ )
{
reset($map_dist);
while( list($key) = @each($map_dist))
{
$temp = explode ('-', $key);
if ($temp[0] == $where[$i]
&& in_array($temp[1], $where) )
{
array_push($queue, $key);
}
}
while ( $queue )
{
calc_total_dist($where[$i], 0, array_pop($queue));
}
}
global $result;
echo $result['nodes'] . ' ' . $result['dist'];
//
//functions
//
function add_to_map($from, $to, $dist)
{
global $i, $map_input;
for ( $j = 0; $j < $i; $j++ )
{
if ( $map_input[$j]['from'] == $from
&& $map_input[$j]['to'] == $to
&& $map_input[$j]['dist'] > $dist)
{
break;
}
}
$map_input[$j]['from'] = $from;
$map_input[$j]['to'] = $to;
$map_input[$j]['dist'] = $dist;
if ( $j == $i )
{
$i++;
}
}
function calc_dist($nodes, $place, $start, $cur_dist = 0)
{
global $map_dist,$map_input;
$to = $map_input[$place]['to'];
$nodes .= $to;
$cur_dist += $map_input[$place]['dist'];
if ( isset($map_dist[$start . '-' . $to]) )
{
$map_dist[$start . '-' . $to] = ($map_dist[$start . '-' . $to] > $cur_dist ) ? $cur_dist : $map_dist[$start . '-' . $to];
} else
{
$map_dist[$start . '-' . $to] = $cur_dist;
}
for ( $i = 0; isset($map_input[$i]['dist']); $i++ )
{
if ( $map_input[$i]['from'] == $to && !strchr( $nodes, $map_input[$i]['to'] ) )
{
calc_dist($nodes, $i, $start, $cur_dist);
}
}
}
function calc_total_dist($nodes_yet, $total_dist, $array_key )
{
global $where, $map_dist, $result, $nodes_len;
$total_dist += $map_dist[$array_key];
$point = explode( '-', $array_key);
$nodes_yet .= ' ' . $point[1];
if ( strlen($nodes_yet) == $nodes_len )
{
if ( isset($result['nodes']) )
{
if ($total_dist < $result['dist'])
{
$result['dist'] = $total_dist;
$result['nodes'] = $nodes_yet;
}
}
else
{
$result['dist'] = $total_dist;
$result['nodes'] = $nodes_yet;
}
}
else
{
$queue = array();
for ($i=0;isset($where[$i]);$i++)
{
if( !strchr( $nodes_yet, $where[$i]) )
{
reset($map_dist);
while( list($key) = @each($map_dist) )
{
if ( $key == $point[1] . '-' . $where[$i] )
{
array_push($queue, $key);
}
}
while ($queue)
{
calc_total_dist($nodes_yet, $total_dist, array_pop($queue) );
}
}
}
}
}
?>
Back to results
|
|
