我目前正在解决一个 kattis 问题:寻宝，Link 。目标是找到花费最少天数到达宝藏的路径。
我目前使用带有加权顶点的 Dijkstra 算法来计算通往宝藏的最短路线。我定义了一个“节点”类，在其中定义了它的权重以及前一个节点(如果已分配)。我使用 heapq 并需要重写 Node 类中的 lt 方法。
定义最短路线后，我尝试计算完成这条最短路线所需的天数。
我知道这不是罚款代码，抱歉。
定义邻居节点和寻路
def createNode(row):
rl = list()
for x in row:
rl.append(Node(x))
return rl
rows, columns, stamina = map(int, input().split(' '))
treasure_map = list()
for row in range(rows):
treasure_map.append(list(input()))
treasure_map = list(map(createNode, treasure_map))
for x in range(len(treasure_map)):
for y in range(len(treasure_map[x])):
tile = treasure_map[x][y]
# add tile to south link
if x - 1 >= 0 and treasure_map[x - 1][y] is not None:
tile.add_neighbour(treasure_map[x - 1][y])
if y + 1 < len(treasure_map[x]) and treasure_map[x][y + 1] is not None:
tile.add_neighbour(treasure_map[x][y + 1])
if x+1 < len(treasure_map) and treasure_map[x + 1][y] is not None:
tile.add_neighbour(treasure_map[x + 1][y])
if y - 1 >= 0 and treasure_map[x][y - 1] is not None:
tile.add_neighbour(treasure_map[x][y - 1])
visited = list()
nodes = list()
for x in treasure_map:
for y in x:
if y.name is not '#':
nodes.append(y)
heapq.heapify(nodes)
endpoint = None
if len(nodes) < 2:
print(-1)
# Search route with minimum load
while nodes:
curr = heapq.heappop(nodes)
if curr.name is 'G':
endpoint = curr
break
for node in curr.get_neighbours():
if node not in visited and not node.load > stamina:
if curr.weight + curr.load < node.weight:
node.add_previous(curr)
visited.append(curr)
heapq.heapify(nodes)
计算从开始到结束所需天数的代码:(我再次知道它可以更好)
if endpoint is not None:
nexNode = endpoint.previous
found = False
stamina_to_use = list()
while nexNode:
if nexNode.name == "S":
# Maybe count the day here
found = True
stamina_to_use.append(nexNode.load)
nexNode = nexNode.previous
days = 1
curr = stamina
counter = 0
stamina_to_use.reverse()
# Count the number of days needed for finishing
while stamina_to_use:
tocheck = stamina_to_use.pop()
# print("Current days: {}, current stamina: {},stamina to withdraw {}".format(
# days, curr, tocheck))
if curr > stamina:
print(-1)
break
if (curr - tocheck) < 0:
days += 1
curr = stamina
curr -= tocheck
if found:
print(days)
else:
print(-1)
else:
print(-1)
结果实际上正如我预期的那样，根据我自己的测试用例以及kattis上的测试用例，我得到了最短路径并得到了正确的天数。但由于某种原因，当我将项目提交给kattis时，前8个左右的测试用例通过了，然后我突然得到:“错误答案”，我不知道我的思维或代码错误在哪里。我的方法是正确的还是应该使用不同的方法？或者只是在计算天数时犯了一个简单的错误？
提前致谢
最佳答案
这是一个几乎有效的解决方案，只是缺少一个小检查。
这样你就需要弄清楚它的作用:)
BIG_NUMBER = 9999
STAMINA_COST = {'F': 2, 'M': 3}
def maybe_update(field1, field2, maze, time_taken, n, m, k, updated_fields):
i1, j1 = field1
i2, j2 = field2
if not (0 <= i2 < n and 0 <= j2 < m):
# Out of bounds
return
field = maze[i2][j2]
if field == '#':
# Can not walk on river
return
days_taken, stamina_taken = time_taken[i1][j1]
stamina_to_move = STAMINA_COST.get(field, 1)
stamina_taken += stamina_to_move
if k < stamina_taken:
days_taken += 1
stamina_taken = stamina_to_move
new_time_taken = (days_taken, stamina_taken)
if new_time_taken < time_taken[i2][j2]:
time_taken[i2][j2] = new_time_taken
updated_fields.add((i2, j2))
def main():
# Read input
n, m, k = map(int, input().split())
maze = []
for i in range(n):
line = input()
maze.append(line)
# Create map of how long it takes to get somewhere
# Each field has (days_spent, stamina_spent)
time_taken = []
for i in range(n):
time_taken.append([(BIG_NUMBER, BIG_NUMBER) for j in range(m)])
# Look for the start and mark it as (1, 0), also look for the gold
updated_fields = set()
for i in range(n):
for j in range(m):
if maze[i][j] == 'S':
time_taken[i][j] = (1, 0)
updated_fields.add((i, j))
elif maze[i][j] == 'G':
gold_at = (i, j)
# BFS to propagate time_taken
while updated_fields:
i, j = updated_fields.pop()
maybe_update((i, j), (i + 1, j), maze, time_taken, n, m, k, updated_fields)
maybe_update((i, j), (i - 1, j), maze, time_taken, n, m, k, updated_fields)
maybe_update((i, j), (i, j + 1), maze, time_taken, n, m, k, updated_fields)
maybe_update((i, j), (i, j - 1), maze, time_taken, n, m, k, updated_fields)
# Print days taken to get to the gold
i, j = gold_at
days_taken = time_taken[i][j][0]
print(-1 if days_taken == BIG_NUMBER else days_taken)
if __name__ == '__main__':
main()
关于python - 使用加权顶点计算图中的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58009822/