CF721C Journey 求教

闲聊吹水
1

https://codeforces.com/contest/721/problem/C

import dataclasses
from collections import defaultdict

num_nodes, num_routes, MAX_DISTANCE = map(int, input().strip().split())
routes = defaultdict(list)


@dataclasses.dataclass
class TreeNode:
    id: int
    distance: int
    num_hops: int
    ancestor: object


for _ in range(num_routes):
    u, v, t = map(int, input().strip().split())
    routes[u].append((v, t))
root = TreeNode(1, 0, 1, None)

destination_nodes = []

next_level = []
for v, t in routes[1]:
    new_node = TreeNode(v, t, 2, root)
    next_level.append(new_node)
    if v == num_nodes:
        destination_nodes.append(new_node)

depth = 2
while next_level:
    depth += 1
    new_level = []
    for node in next_level:
        for v, t in routes[node.id]:
            if t + node.distance > MAX_DISTANCE:
                continue
            new_node = TreeNode(v, t + node.distance, depth, node)
            new_level.append(new_node)
            if v == num_nodes:
                destination_nodes.append(new_node)
    next_level = new_level

solution_node = destination_nodes[0]
for node in destination_nodes[1:]:
    if node.num_hops > solution_node.num_hops:
        solution_node = node
print(solution_node.num_hops)
node = solution_node
path = []
while node.ancestor is not None:
    path.append(node.id )
    node = node.ancestor
path.append(1)
print(' '.join(map(str, reversed(path))))

搜索树太大了，在 case11 上 MLE，有没有同学教教我这种怎么用 DP