谷歌启动卡车交付部分正确的答案

Question

我试图解决来自Google Kick Start 2021 Round B的卡车交付问题(第四个问题)我发现我的代码有一个问题，我无法解决;

import sys
import math
sys.stdin = open('input.txt', 'r')

def solve(index):
if index == 0 :
return
else:
for j in range(len(roads)):
if roads[j][0] == index:
if roads[j][2] <= w:
fines.append(roads[j][3])
solve(roads[j][1])

T = int(input())
for case in range(1, T+1):
n, q = [int(x) for x in input().split(" ")]
roads = []
for rd in range(n-1):
road = [int(x) for x in input().split(" ")]
if road[0] < road[1]:
temp = road[1]
roads.append([road[1], road[0], road[2], road[3]])
else:
roads.append(road)
roads.sort(reverse=True)
result = ""
for query in range(q):
c, w = [int(x) for x in input().split(" ")]
fines = []
solve(c)
if len(fines) != 0:
result += str(math.gcd(*fines)) + " "
else:
result += "0 "
print("Case #{}: {}".format(case, result))

我从样本案例中得到了部分正确的答案，我的输出是;

Case #1: 1 0 0 5 7 
Case #2: 0 5

正确的输出应该是;

Case #1: 1 4 0 5 7
Case #2: 10 5

由于某种原因，我的递归没有在case 1 day 1和case 2 day 0中添加fine。你们能发现问题吗?也请随时告诉我代码中的不良实践等。PS:我不是在寻找这个问题的最佳答案，我只是想自己解决它

Answer 1

这两个测试用例失败的原因是您的solve代码一旦发现一条不需要支付通行费的道路就退出递归。但这是不对的:通往1号城市的其余道路可能仍然有其他道路需要收费。

因此将递归调用移出if块，如下所示:

if roads[j][2] <= w:
fines.append(roads[j][3])
solve(roads[j][1])

虽然这将解决您遇到的问题，但前面还有更多的问题:

你的算法假设从城市k到城市#1的路径总是从一个数字较大的城市到一个数字较小的城市。虽然这是2个样例测试用例的情况，但这并不能保证。这条路很可能从城市20到城市80，然后到城市1。

要解决这个问题，你必须改变你的方法。我建议创建一个列表，其中索引是一个城市编号，值是一个元组(parent, maxweight, toll)，这样parent是城市的父节点，当树扎根作为根节点城市#1。

为了制作这个列表，我建议首先创建一个邻接表，然后以深度优先的方式从城市1开始遍历该图。在遍历您可以注册的"upward"边指向根，并创建上一段描述的数据结构。

下面是一些(未经测试的)代码:

def solve(parent, city, weight):
fines = []
while city > 1:
if weight >= parent[city][1]:
fines.append(parent[city][2])
city = parent[city][0]
return math.gcd(*fines) if fines else 0

def buildtree(roads):
# Adjacency list:
adj = [[] for _ in range(n + 1)]  # index is city number (1 .. N).  
for city1, city2, maxweight, toll in roads:
# Add road in both directions to adjacency list
adj[city1].append((city2, maxweight, toll))
adj[city2].append((city1, maxweight, toll))
# Each node has only one parent in a rooted tree. 
#   Find that parent for each node, when node #1 is the root:     
visited = [False] * (n + 1)
parent = [None] * (n + 1)
def recur(city):
visited[city] = True
for nextcity, maxweight, toll in adj[city]:
if not visited[nextcity]:
parent[nextcity] = (city, maxweight, toll)
recur(nextcity)
recur(1)  # build `parent` data structure
return parent

sys.stdin = open('input.txt', 'r')
numcases = int(input())
for case in range(1, numcases + 1):
numcities, numqueries = [int(x) for x in input().split(" ")]

roads = [
[int(x) for x in input().split(" ")]
for road in range(numcities - 1)
]
queries = [
[int(x) for x in input().split(" ")]
for query in range(numqueries)
]
parent = buildtree(roads)
result = " ".join(
str(solve(parent, city, weight)) for city, weight in queries
)
print("Case #{}: {}".format(case, result))