设计公司企业站,网站开发和上传中错误的是,坪山附近网站建设,六安在线网文章目录 97.小明逛公园127.骑士的攻击 97.小明逛公园
之前的题目都是只有一个出发点和到达点#xff0c;这道题是有多个起始对#xff0c;用之前的算法把每一对结果算出来也是可行的#xff0c;在这里使用Floyd算法。 本质上是一种动态规划#xff0c;dp数组dp[i][j][k]中… 文章目录 97.小明逛公园127.骑士的攻击 97.小明逛公园
之前的题目都是只有一个出发点和到达点这道题是有多个起始对用之前的算法把每一对结果算出来也是可行的在这里使用Floyd算法。 本质上是一种动态规划dp数组dp[i][j][k]中的ij两点在以(1~k)中的点作为中间结点的时候的最小距离递推公式是dp[i][j][k]min(dp[i][k][k-1]dp[k][j][k-1], dp[i][j][k-1])遍历顺序是k在最外ij在内。本质上是因为dp[i][k][k-1]这些中间量还可能是由k更小的时候的组合推断出来的所以对于所有的i和jk都应该是从小到大递增推导所有i和j的状态所以k在最外层。
n, m map(int, input().split())
grid [[[float(inf)] * (n1) for _ in range(n1)] for _ in range(n1)]
for i in range(m):u, v, w map(int, input().split())grid[u][v][0] wgrid[v][u][0] w
q int(input())
plans []
for i in range(q):start, end map(int, input().split())plans.append([start, end])for k in range(1, n1):for i in range(1, n1):for j in range(1, n1):grid[i][j][k] min(grid[i][j][k-1], grid[i][k][k-1] grid[k][j][k-1])for plan in plans:if grid[plan[0]][plan[1]][-1] ! float(inf):print(grid[plan[0]][plan[1]][-1])else:print(-1)127.骑士的攻击
这道题使用的是Astar算法是在BFS的基础上进行了一定的优化。普通的BFS也能做但是在广度搜索的时候会有很多的浪费因此关键就在于每次如何选择朝向目标移动的最近的点。Astar通过计算每个点的预估距离并用小顶堆进行排序从而使得每次取出来的都是当前可能最小距离的点。在这题使用欧氏距离最合适总距离是点距离原点的欧氏距离加上到目标点的欧氏距离。
import heapqn int(input())
directions [[-2, 1], [-1, 2], [1, 2], [2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1]]
Distance lambda x, y, tar_x, tar_y: (x - tar_x) ** 2 (y - tar_y) ** 2class Knight:def __init__(self, a1, a2, g0, f0, h0):self.x a1self.y a2self.g gself.f f self.h hdef __lt__(self, k):return self.f k.fdef __str__(self):return fKnight:{self.x},{self.y}def bfs(grid, knight, target):heap []heapq.heappush(heap, knight)while heap:cur heapq.heappop(heap)if cur.x target[0] and cur.y target[1]:returnfor d in directions:next_x cur.x d[0]next_y cur.y d[1]if next_x 1 or next_x len(grid) or next_y 1 or next_y len(grid[0]):continueif not grid[next_x][next_y]:grid[next_x][next_y] grid[cur.x][cur.y] 1next_knight Knight(next_x, next_y)next_knight.g cur.g 5next_knight.h Distance(next_x, next_y, target[0], target[1])next_knight.f next_knight.g next_knight.h heapq.heappush(heap, next_knight)for i in range(n):a1, a2, b1, b2 map(int, input().split())grid [[0] * 1001 for _ in range(1001)]knight Knight(a1, a2)knight.h Distance(a1, a2, b1, b2)knight.f knight.g knight.hbfs(grid, knight, [b1, b2])print(grid[b1][b2])
