小猫咪吃python

# AcWing 851. spfa 求最短路 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。 数据保证不存在负权回路。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式 输出一个整数，表示 1 号点到 n 号点的最短距离。 如果路径不存在，则输出 impossible。 数据范围 1≤n,m≤105, 图中涉及边长绝对值均不超过...

前置知识：图论基础之 Dijkstra 求最短路 # AcWing 853. 有边数限制的最短路 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。 注意：图中可能 存在负权回路 。 输入格式 第一行包含三个整数 n,m,k。 接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 点的编号为 1∼n。 输出格式 输出一个整数，表示从 1 号点到 n 号点的最多经过 k...

# AcWing 849. Dijkstra 求最短路 I（图论中的基础最短路问题） 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式 输出一个整数，表示 1 号点到 n 号点的最短距离。 如果路径不存在，则输出 −1。 数据范围 1≤n≤500, 1≤m≤105, 图中涉及边长均不超过 10000。 输入样例： 3...

# 前缀和的作用 解决的问题：给定一个数组 nums 和 m 次询问，两个整数 left 和 right，表示一个询问的区间范围。 # 暴力解法 从题面上分析这种问题暴力做法想要求出来基本上要遍历 nums 中到 right 的数，然后一个个相加到 left，在一个个相加到 right。在暴力的算法中可以看到我们两次计算了 nums [0....left] 的部分，并且询问次数 M+1，就需要多遍历两次。 # 前缀和优化 前缀和的思路其实就是预处理 nums 中每个数得出来他们与前面所有元素相加之和为新的元素，这些新的元素就成了前缀和数组。利用该数组轻松的就能在 O (1)...