Xiran

<?php

/*
 * Комната 0 введена для унификации алгоритма.
 * Из неё можно попаст в любой выход, в неё попасть из других комнат нельзя.
 */
const NODES = [
    0 => ['battleTime' => 0, 'loot' => 0],
    1 => ['battleTime' => 5, 'loot' => 15],
    2 => ['battleTime' => 2, 'loot' => 1],
    3 => ['battleTime' => 3, 'loot' => 5],
    4 => ['battleTime' => 3, 'loot' => 6],
    5 => ['battleTime' => 4, 'loot' => 7],
    6 => ['battleTime' => 5, 'loot' => 9],
    7 => ['battleTime' => 7, 'loot' => 16],
    8 => ['battleTime' => 2, 'loot' => 3],
    9 => ['battleTime' => 0, 'loot' => 0],
    10 => ['battleTime' => 0, 'loot' => 0],
];

const ROUTE_TIMES = [
    0 => [9 => 0, 10 => 0],
    1 => [2 => 1],
    2 => [1 => 1, 8 => 2, 9 => 3, 4 => 1],
    3 => [9 => 2, 4 => 4],
    4 => [3 => 4, 2 => 1, 5 => 3],
    5 => [4 => 3, 10 => 1],
    6 => [10 => 4, 7 => 4],
    7 => [8 => 4, 6 => 4],
    8 => [2 => 2, 7 => 4, 10 => 6],
    9 => [3 => 2, 2 => 3],
    10 => [5 => 1, 8 => 6, 6 => 4],
];

const MAX_LIFETIME = 25;

function findRoute(array $state): array
{
    $bestState = $state;
    foreach (ROUTE_TIMES[$state['currentNode']] as $nextNode => $travelTime) {
        $nodeTime = $state['lifetime'] + $travelTime +
            (in_array($nextNode, $state['route']) ? 0 : NODES[$nextNode]['battleTime']);
        if ($nodeTime > MAX_LIFETIME) {
            continue;
        }
        $nodeState = findRoute([
            'lifetime' => $nodeTime,
            'currentNode' => $nextNode,
            'wealth' => $state['wealth'] + (in_array($nextNode, $state['route']) ? 0 : NODES[$nextNode]['loot']),
            'route' => [...$state['route'], $nextNode],
        ]);
        if ($nodeState['wealth'] > $bestState['wealth']) {
            $bestState = $nodeState;
        }
    }
    return $bestState;
}

$state = findRoute([
    'lifetime' => 0,
    'currentNode' => 0,
    'wealth' => 0,
    'route' => [],
]);

echo "Route: ", implode(' => ', array_reverse($state['route'])), "\n";
echo "Wealth: ", $state['wealth'], "\n";
echo "Time: ", $state['lifetime'], "\n";

Route: 8 => 2 => 1 => 2 => 4 => 5 => 10
Wealth: 32
Time: 25