QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91500 | #5102. Dungeon Crawler | Serdahsufyan | WA | 15ms | 8200kb | Python3 | 2.5kb | 2023-03-28 23:25:11 | 2023-03-28 23:25:13 |
Judging History
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: ''