QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91500#5102. Dungeon CrawlerSerdahsufyanWA 15ms8200kbPython32.5kb2023-03-28 23:25:112023-03-28 23:25:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-28 23:25:13]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:8200kb
  • [2023-03-28 23:25:11]
  • 提交

answer

from collections import defaultdict

def solve():
    n, q = map(int, input().split())
    adj_list = defaultdict(list)
    weights = {}
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        adj_list[u].append(v)
        adj_list[v].append(u)
        weights[(u, v)] = w
        weights[(v, u)] = w
    
    # Compute min_time values
    min_time_values = {}
    
    def min_time(node, visited_key, visited_trap):
        if (node, visited_key, visited_trap) in min_time_values:
            return min_time_values[(node, visited_key, visited_trap)]
        
        # Base cases
        if visited_key and not visited_trap and node == trap:
            return float('inf')
        if visited_trap and not visited_key and node == key:
            return float('inf')
        if visited_key and visited_trap and (node == key or node == trap):
            return 0
        if node not in adj_list:
            return float('inf')
        
        # Recursive cases
        min_time_with_key = float('inf')
        min_time_without_key = float('inf')
        for child in adj_list[node]:
            if child == parent[node]:
                continue
            rest_of_tree = [n for n in adj_list[node] if n != child] + [parent[node]]
            min_time_with_key = min(min_time_with_key,
                                    min_time(child, True, visited_trap) +
                                    min_time(rest_of_tree, visited_key, True))
            min_time_without_key = min(min_time_without_key,
                                       min_time(child, visited_key, visited_trap) +
                                       min_time(rest_of_tree, True, True))
        result = weights[(parent[node], node)] + min(min_time_with_key, min_time_without_key)
        min_time_values[(node, visited_key, visited_trap)] = result
        return result
    
    # Process scenarios
    for _ in range(q):
        start, key, trap = map(int, input().split())
        parent = defaultdict(int)
        visited = defaultdict(bool)
        stack = [start]
        while stack:
            node = stack.pop()
            visited[node] = True
            for child in adj_list[node]:
                if child != parent[node]:
                    parent[child] = node
                    stack.append(child)
        if not visited[key] or not visited[trap]:
            print('impossible')
        else:
            print(min_time(start, False, False) + weights[(parent[start], start)])

詳細信息

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 8200kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:


result:

wrong answer 1st lines differ - expected: '316', found: ''