Code of kevin
<?php
/*
author: Kevin Hjelden
forum account: FryGuy
email address: phpeditor@burntpopcorn.net
description:
solution for contest B4 located at:
https://www.php-editors.com/contests.php
it's probably a loser but it was fun writing!
have fun!
*/
$costtable = array();
function addcost($from, $to, $cost) {
global $costtable;
if (isset($costtable[$from])) {
if (isset($costtable[$from][$to])) {
$costtable[$from][$to] = min($costtable[$from][$to], $cost);
} else {
$costtable[$from][$to] = $cost;
}
} else {
$costtable[$from] = array();
$costtable[$from][$to] = $cost;
}
}
function getcost($from, $to) {
if (isset($costtable[$from]) && isset($costtable[$from][$to]))
return $costtable[$from][$to];
else
return 9999;
}
function dijikstra(&$from, &$dests) {
global $costtable;
// generate the initial table
$d = array();
foreach ($costtable as $key=>$value) {
$d[$key] = array(
"cost" => 9999,
"solved" => false
);
}
$d[$from]["cost"] = 0;
$todone = 0;
$todo = count($dests);
while ($todone<$todo) {
// find min elem in d-table
$best = 9999; $elem = 0;
foreach ($d as $key=>$value) {
if ($value["cost"] < $best && $value["solved"] == false) {
$best = $value["cost"];
$elem = $key;
}
}
if ($best == 9999)
break;
// pass on elements from here
if (isset($costtable[$elem])) {
foreach ($costtable[$elem] as $dest=>$cost) {
if ($d[$dest]["solved"] == false)
$d[$dest]["cost"] = min($d[$dest]["cost"], $d[$elem]["cost"] + $cost);
}
}
// mark as solved
$d[$elem]["solved"] = true;
if (in_array($elem, $dests))
$todone++;
}
// pretty it up
$ret = array();
foreach ($d as $key=>$value) {
if ($value["solved"] && $value["cost"] != 9999)
$ret[$key] = $value["cost"];
}
return $ret;
}
$fp = fopen("map.txt", "r");
while (!feof($fp)) {
$line = strtoupper(trim(fgets($fp, 4096)));
list($from, $cost, $to, $dirs) = explode(" ", $line);
addcost($from, $to, $cost);
if ($dirs == 2)
addcost($to, $from, $cost);
}
fclose($fp);
$fp = fopen("dest.txt", "r");
$dests = strtoupper(trim(fgets($fp, 4096)));
$dests = explode(" ", $dests);
fclose($fp);
$bestcosttable = array();
foreach ($dests as $dest) {
$bestcosttable[$dest] = dijikstra($dest, $dests);
}
function leftsort($a, $b) {
global $from, $bestcosttable;
$a1 = $bestcosttable[$from][$a];
$b1 = $bestcosttable[$from][$b];
return $a1 == $b1?0:($a1 > $b1?1:-1);
}
$bestcost = 9999;
$bestpath = array();
function runpermute(&$used, &$left, $cost) {
global $bestcosttable, $bestcost, $bestpath, $sortfrom;
if ($cost > $bestcost)
return;
if (!count($left)) {
// end of the line.. save this one if it's good.
if ($cost < $bestcost) {
$bestcost = $cost;
$bestpath = $used;
}
return;
}
// permute!
$from = count($used)?$used[count($used)-1]:"";
if ($from) {
$sortfrom = $from;
usort($left, "leftsort");
}
$a = $used;
$c = count($used);
foreach ($left as $key=>$elem) {
if ($from && !isset($bestcosttable[$from][$elem]))
continue;
$a[$c] = $elem;
$b = $left;
unset($b[$key]);
$nextcost = ($from?$bestcosttable[$from][$elem]:0);
runpermute($a, $b, $cost + ($from?$bestcosttable[$from][$elem]:0));
}
}
$holder = array();
runpermute($holder, $dests, 0);
echo implode(" ", $bestpath)." $bestcost\n";
?>
Back to results
|
|
