[2025 Day11 (Part2)] svr -> fft taking too much time

type Graph = dict[str, set[str]]
def read_input(file_name: str):
    graph: Graph = dict()
    with open(file_name, "r") as f:
        for line in f.readlines():
            source, sinks = line.strip("\n").split(": ")
            graph[source] = set()
            for sink in sinks.split(" "):
                graph[source].add(sink.strip())


    return graph


def dfs(graph: Graph, dp: dict[str, int], node: str, end: str) -> int:
    if node == end: return 1
    if end != 'out' and node == 'out': return 0
    
    if dp[node] > 0: return dp[node]
    
    result = 0
    for sink in graph[node]:
        result += dfs(graph, dp, sink, end)


    dp[node] = result
    return dp[node]


def main() -> None:
    graph = read_input("11/input.txt")


    dp = {source: 0 for source in graph.keys()}
    x = dfs(graph, dp, 'svr', 'dac'); print(x, end=" ")
    dp = {source: 0 for source in graph.keys()}
    y = dfs(graph, dp, 'dac', 'fft'); print(y, end=" ")
    dp = {source: 0 for source in graph.keys()}
    z = dfs(graph, dp, 'fft', 'out'); print(z)


    dp = {source: 0 for source in graph.keys()}
    a = dfs(graph, dp, 'svr', 'fft'); print(a, end=" ")
    dp = {source: 0 for source in graph.keys()}
    b = dfs(graph, dp, 'fft', 'dac'); print(b, end=" ")
    dp = {source: 0 for source in graph.keys()}
    c = dfs(graph, dp, 'dac', 'out'); print(c)


    print(f"\nPaths: {min(a, b, c) + min(x, y, z)}")