{"topic":{"id":13284,"title":"CF721C Journey 求教","slug":"topic","categoryId":4,"createdAt":"2024-08-20 08:48:47.03945","bumpedAt":"2024-08-20 08:48:47.227902","views":127,"postsCount":1,"highestPostNumber":1,"likeCount":0,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"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.dataclas…","deletedAt":null,"isAnonymous":false,"category":{"id":4,"name":"谈笑风生","slug":"general","color":"25AAE2"},"author":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif"},"tags":[]},"posts":[{"id":38852,"postNumber":1,"raw":"https://codeforces.com/contest/721/problem/C\n\n```python\nimport dataclasses\nfrom collections import defaultdict\n\nnum_nodes, num_routes, MAX_DISTANCE = map(int, input().strip().split())\nroutes = defaultdict(list)\n\n\n@dataclasses.dataclass\nclass TreeNode:\n id: int\n distance: int\n num_hops: int\n ancestor: object\n\n\nfor _ in range(num_routes):\n u, v, t = map(int, input().strip().split())\n routes[u].append((v, t))\nroot = TreeNode(1, 0, 1, None)\n\ndestination_nodes = []\n\nnext_level = []\nfor v, t in routes[1]:\n new_node = TreeNode(v, t, 2, root)\n next_level.append(new_node)\n if v == num_nodes:\n destination_nodes.append(new_node)\n\ndepth = 2\nwhile next_level:\n depth += 1\n new_level = []\n for node in next_level:\n for v, t in routes[node.id]:\n if t + node.distance > MAX_DISTANCE:\n continue\n new_node = TreeNode(v, t + node.distance, depth, node)\n new_level.append(new_node)\n if v == num_nodes:\n destination_nodes.append(new_node)\n next_level = new_level\n\nsolution_node = destination_nodes[0]\nfor node in destination_nodes[1:]:\n if node.num_hops > solution_node.num_hops:\n solution_node = node\nprint(solution_node.num_hops)\nnode = solution_node\npath = []\nwhile node.ancestor is not None:\n path.append(node.id )\n node = node.ancestor\npath.append(1)\nprint(' '.join(map(str, reversed(path))))\n```\n搜索树太大了，在 case11 上 MLE，有没有同学教教我这种怎么用 DP","cooked":"

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

import dataclasses\nfrom collections import defaultdict\n\nnum_nodes, num_routes, MAX_DISTANCE = map(int, input().strip().split())\nroutes = defaultdict(list)\n\n\n@dataclasses.dataclass\nclass TreeNode:\n    id: int\n    distance: int\n    num_hops: int\n    ancestor: object\n\n\nfor _ in range(num_routes):\n    u, v, t = map(int, input().strip().split())\n    routes[u].append((v, t))\nroot = TreeNode(1, 0, 1, None)\n\ndestination_nodes = []\n\nnext_level = []\nfor v, t in routes[1]:\n    new_node = TreeNode(v, t, 2, root)\n    next_level.append(new_node)\n    if v == num_nodes:\n        destination_nodes.append(new_node)\n\ndepth = 2\nwhile next_level:\n    depth += 1\n    new_level = []\n    for node in next_level:\n        for v, t in routes[node.id]:\n            if t + node.distance > MAX_DISTANCE:\n                continue\n            new_node = TreeNode(v, t + node.distance, depth, node)\n            new_level.append(new_node)\n            if v == num_nodes:\n                destination_nodes.append(new_node)\n    next_level = new_level\n\nsolution_node = destination_nodes[0]\nfor node in destination_nodes[1:]:\n    if node.num_hops > solution_node.num_hops:\n        solution_node = node\nprint(solution_node.num_hops)\nnode = solution_node\npath = []\nwhile node.ancestor is not None:\n    path.append(node.id )\n    node = node.ancestor\npath.append(1)\nprint(' '.join(map(str, reversed(path))))\n

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

\n","createdAt":"2024-08-20 08:48:47.227902","updatedAt":"2024-12-22 15:27:30.651246","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":174,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif","admin":true,"moderator":false,"signatureRaw":"","signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":1,"hasUrlPostNumber":false}