摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10911人学习

全部文章（共5篇）

题解 | #单源最短路# 来自专栏

题目的主要信息：在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径如果 1 无法到 n ，输出 -1 图没有自环，可能有重边方法一：floyd算法具体做法：可以用floyd算法计算任意两个节点之间的最短路径，然后取1-n的即可。用矩阵w表示任意两个节点...

C++ 图

2021-12-09

3 550

题解 | #郊区春游# 来自专栏

题目的主要信息：一共nnn个点，mmm条道路连接，每条道路花费会随着道路连接情况给出给出RRR个要前往的点，前往顺序不定，问什么路线花费最少下面解法中我们用距离代替长度具体做法：首先我们用邻接矩阵来表示这个图，矩阵记录两两点之间的距离，初始化为最大值，自己到自己都是0，再根据输入更新直...

C++ 动态规划图

2021-11-01

2 551

题解 | #反复横跳# 来自专栏

题目的主要信息：一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树计算从任意点出发并访问完所有节点经过边的权值之和的最小值分析：首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝，...

动态规划图递归 dfs 树的直径

2021-09-14

1 612

题解 | #牛妹的野菜（权值最大的路径）# 来自专栏

思路：题目的主要信息：一个有向无环图，路径是单向从小序号到大序号，每个节点有权值求图中一条权值和最大的路径，并以字符串输出这条路径方法一：动态规划具体做法：我们可以用动态规划的方式来解决。首先利用给出的路径数组构建一个邻接矩阵，我们以weigh数组表示从每个节点开始的最长路径的长度，pa...

空间记忆搜索递归动态规划 dfs 图

2021-09-03

0 660

题解 | #回路# 来自专栏

题目的主要信息： n个节点，m条边，数组edge记录的是有边的两个节点判断这个图是否有从1号节点开始的回路方法一：dfs 具体做法：首先我们构建图。然后从节点1开始进行深度优先搜索，遍历与其相连的每一个节点，每到一个节点不能遍历前序节点或者已经访问过的，然后每次需要判断是否回到了节点1，如...

回路图 bfs dfs 递归队列

2021-08-26

0 711