Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of oliver
<?php set_time_limit(60); $time_start = getmicrotime();
/********************************************************************************************
* *
* AUTOR: Oliver Heil (oheil@ecc-gmbh.de) *
* *
* FILE: pizza_dude.php *
* CREATE: 2003/08/14 *
* *
********************************************************************************************/
// ARRAY's FOR LATER USE
$map = $dest = $routes = array();
// READ "map.txt" AND BUILD MAP MATRIX
$fmap = fopen("map.txt", "r");
while (!feof($fmap)) {
$item = explode(" ", strtoupper(chop(fgets($fmap))));
$map[$item[0]][$item[2]] = $item[1];
if ($item[3] == 2) {
$map[$item[2]][$item[0]] = $item[1];
}
}
fclose($fmap);
$sm = count($map);
// KALKULATE MAP MATRIX (Floyd Algorithmus / Adjazenzmatrix)
for ($k=0; $k < $sm; $k++) { $kc = chr($k+65);
for ($i=0; $i < $sm; $i++) { $ic = chr($i+65);
for ($j=0; $j < $sm; $j++) { $jc = chr($j+65);
if ($i == $j) $map[$ic][$jc] = "x";
else {
if (empty($map[$ic][$jc])) $map[$ic][$jc] = 99999999999999999999; // INFTY ...
else $map[$ic][$jc] = min($map[$ic][$jc], $map[$ic][$kc] + $map[$kc][$jc]);
}
}
}
}
// READ "dest.txt" IN "destinations" ARRAY FOR DELIVERY
$fdest = fopen("dest.txt", "r"); $destinations = explode(" ", strtoupper(chop(fread($fdest, filesize("dest.txt"))))); fclose($fdest);
// BUILD DESTINATION MATRIX
$u=0;
foreach($destinations as $i) { $v=0;
foreach($destinations as $j) {
$dest[$u][$v++] = strval($map[$i][$j]);
}
$mapping[$i] = $u++;
}
$sd = count($dest);
// LOOP ALL DESTINATION NODES AS BEGINNING NODE
foreach ($destinations as $begin) {
// INITIALIZE array $VISITED, int $SUM, string $ROUTE
$visited = array_flip($destinations); $sum = 0; $route = "";
// SET BEGINNING NODE AS AKTUELL AND UNSET IT IN VISITED ARRAY
unset($visited[($aktuell = $begin)]);
// LOOP ALL VISITED NODES
do { $ways = array();
// APPEND AKTUELL NODE ON ROUTE
$route.= $aktuell." ";
// LOOP ALL NOT VISITED NODES
foreach ($visited as $visit_k=>$visit_v) {
// CALL "Branch_and_Bound" FUNKTION AND STORE RESULTS IN WAYS ARRAY
$ways[$aktuell.$visit_k] = Branch_and_Bound($dest, $sd, $mapping[$aktuell], $visit_v);
}
// FIND SHORTEST NODE
$shortest = substr(array_search(min($ways), $ways), -1);
// SUMMARIZE WAYS
$sum += $dest[$mapping[$aktuell]][$mapping[$shortest]];
// SET SHORTEST NODE AS AKTUELL AND UNSET IT IN VISITED ARRAY
unset($visited[$aktuell = $shortest]);
// HAS BEEN ALL NOTES VISITED ?
} while (count($visited) > 0);
// FILL ROUTES ARRAY
$routes[$route.$aktuell] = $sum;
}
// DEBUG
//print_r($routes);
// SHOW SHORTEST ROUTE(S)
echo "\nShortest Route(s):\n\n";
foreach (array_keys($routes, ($min=min($routes))) as $shortest_route) {
echo $shortest_route." [".$min."]\n";
}
// SHOW RUNTIME
echo "\nRuntime: ".(getmicrotime() - $time_start)."\n";
// FUNKTION BRANCH_AND_BOUND
function Branch_and_Bound($dest, $sd, $d1, $d2) {
$dest[$d2][$d1] = "x";
for ($i=0; $i < $sd; $i++) {
for ($j=0; $j < $sd; $j++) {
if (($i == $d1) && ($j != $d2) || ($i != $d1) && ($j == $d2)) $dest[$i][$j] = "x";
// DEST_T (DEST MATRIX TRANSPONIERT)
$dest_T[$j][$i] = $dest[$i][$j];
}
}
// SUMMARIZE MIN's FROM DEST MATRIX AND DEST_T MATRIX
for ($i=0; $i < $sd; $i++) {
$dest_min += min($dest[$i]); $dest_T_min += min($dest_T[$i]);
}
return min($dest_min, $dest_T_min);
}
// GETMICROTIME()
function getmicrotime(){
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}
// END © 2003 Oliver Heil
?>
Back to results
|
|
|
