proboscidea volcanium

approach

the valves are parsed into a flow rate per valve and an adjacency list. a memoized dp(n, o, t, e) takes the current valve, a bitmask of opened valves, the minutes left and how many extra explorers are still to come. each minute it either opens the current valve, adding its flow times the remaining minutes, or walks to a neighbour.

part 1 is dp("AA", 0, 30, 0). part 2 gives 26 minutes and one extra explorer: when the first one runs out of time, the search restarts from AA with a fresh 26 minutes but keeps the same bitmask, so the elephant can't reopen valves that are already open.

the trick

run the two walkers one after the other, passing the opened-valve bitmask from the first to the second.

@lru_cache(None)
def dp(n, o, t, e):
    if t <= 0:
        return 0 if e == 0 else dp("AA", o, 26, e - 1)
    res = 0
    bs = 1 << v2i[n]
    if (bs & o) == 0 and w[n] > 0:
        res = max(res, dp(n, bs | o, t - 1, e) + (w[n] * (t - 1)))

    for nn in d[n]:
        res = max(res, dp(nn, o, t - 1, e))
    return res