在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共6篇）

题解 | #逛公园#

本题要求求路径数，图论的最短路算法可求不了路径数，那么可以想到在图里面使用动态规划的方式去求路径数。在本题里面可以得出从某一点到下一点的路径方式有多少取决去这一点之前的路径数，以及该点和下一点的路径数。那么就可以知道之间可以使用动态规划去求解。但本题有要求路径长度不能超过n+...

C++ 动态规划迪杰斯特拉算法图论最短路径

2023-11-16

2 400

题解 | #传送门#

这题还是再考最短路算法，在这里还是迪杰斯特拉。但难点在于建图，在这里将同一种种类的传送门具化成一个点，拥有这个传送门的可以通过这个传送门进行到达。但在花费上是二倍。还有就是不要使用map<pair<int,int>,int>来保存边。这个数据类型操作会导致这道...

C++ 图论迪杰斯特拉算法最短路

2023-11-08

0 594

题解 | #分层图最短路#

直接建图利用最短路算法去搞。这里首先说一下最短路的几种算法以及各自的用途：迪杰斯特拉算法：求单源最短路的算法，要求图中不能有负边，否则就破坏了这个算法的贪心策略。 SPFA：也是求单源最短路的算法，这个算法在图中有负边的时候可以用，一般如果图中没有负边不用，毕竟是将图中所有点都...

C++ 图迪杰斯特拉算法

2023-11-07

2 489

题解 | #胖胖的牛牛#

因为正在练习图论，所以建图来做吧。可以假设某个各种的上下左右方向都有一个点，那么这些点的道路里面方向改变的，也就是某个格子上下左右相邻直接的道路的长度是1，其余是0。那么就可以转化成起点的四个方向点到终点的四个方向点的求解。那么直接套Dijkstra算法即可。就是建图有那么亿...

C++ 深度优先搜索图论迪杰斯特拉算法

2023-11-06

1 293

题解 | #Rinne Loves Graph#

//迪杰斯特拉算法配合上动态规划 //动态规划的数组为：dp[i][j]。表示到达第i号城镇，穿过了k次所走的最短路 //一定要注意迪杰斯特拉将优先队列里面已经作为最短判断过了不要再判断了。否则会发生很奇怪的错误。 #include <bits/stdc++.h> using&...

C++ 图论动态规划迪杰斯特拉算法

2023-11-02

1 368

题解 | #公交线路#

本题属于Dijkstra算法的模板题。只需要之前迪杰斯特拉算法求出起点s到每个点的最短距离。然后输出s到t的最短距离即可。这里简要说一下迪杰斯特拉算法的原理：迪杰斯特拉算法使用一个贪心的思想，在每一次的路径里面最短的那一个一定是确定的，也就是说不会被其他的路径影响从而边的更短。那么我...

C++ 图论 Dijkstra 迪杰斯特拉算法最短路径算法

2023-11-01

0 399