徐某

用户名：1078110251

访问量：481

签　名：

等　　级
排　　名	4258
经　　验	1486
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	西南石油大学
专　　业

　　自我简介：

TA的其他文章

迪杰斯特拉算法求最小权值
浏览：94

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

迪杰斯特拉算法求最小权值

　　作者: 徐某　　　　发表时间：2023-04-06 19:52:13 浏览：94　|　评论：0　

原题链接：蓝桥杯2020年第十一届省赛真题-作物杂交

总体思路:本质上，我使用了迪杰斯特拉算法。如果没有了解的朋友，只要知道这个算法的功能，给一副图，一个起点，可以求出图上所有点到起点的**最短距离**。
但是在具体的代码细节中，这道题还是需要我们仔细斟酌。
比如存储图的方式，以及这道题的图与一般的不同之处。
首先，观察范围，种子的数量在2000。虽然不大，但是我们基本不可能用邻接矩阵来存放。因为graph[2000][2000]占用了**40万**的空间。
其次，这道题两个种子合成新的种子，如果用邻接矩阵存放，那么我们应该在二维数组中放什么内容呢？一般的图，在graph[i][j]中都存放i,j两点之间的权重。但这个题目存放的是两个种子合成的结果。
因此，我认为用邻接矩阵的方式，无论从空间和对写代码的帮助都有问题。我采用**链表**存储每个种子的合成路径
```cpp
typedef struct mix{
	int second;
	int result;
}mix;
```
这个结构体中，**second**指的是用于合成路径中的另一个种子，**result**指的是合成出来的新种子

下面是一些读入数据的代码块
```cpp
int n, m, k, t;
	cin >> n >> m >> k >> t;
	//n是种类总数 m是最开始有的种子数 k表示可以杂交的方案数 t表示目标编号
	int growtime[2001];//growtime[i]表示编号I的生长时间
	for (int i = 1; i <= n; i++) {
		cin >> growtime[i];
	}
	int ishave[2001];
	for (int i = 1; i <= m; i++) {
		cin >> ishave[i];//ishave[i]存的是第i个拥有的种子 
	}
	//	mixnode* solotions=new mixnode[k+1];
	list<mix>L[2000];
	
	for (int i = 1; i <= k; i++) {
		int first, second;
		list<mix>adj;
		mix node;
		cin >> first >> node.second >> node.result;
		L[first].push_back(node);//L[i]表示第i个种子的杂交方案 
	}
```
对于ishave这个数组，可以将它去掉。因为它的作用好像只有在迪杰斯特拉算法中进行初始化。
从13行开始，就是在读入每个种子的杂交方案。
这是图的邻接表的存储方式。

下面是迪杰斯特拉算法的内容。
````cpp
typedef struct node {
	int id;
	int dist;
}node;
````
```cpp
int DistFromStart[2001];
	memset(DistFromStart, 9999, sizeof(int) * 2001);
	for (int i = 1; i <= m; i++) {
		DistFromStart[ishave[i]] = 0;
	}
	queue <node>q;
	for (int i = 1; i  0) {//可以杂交 
			int product = i.result;
				int TimeCost = max(growtime[cur.id], growtime[i.second]) + max(cur.dist,DistFromStart[i.second]);
				if (TimeCost < DistFromStart[product]) {
					DistFromStart[product] = TimeCost;
					q.push({ product,TimeCost });
				}
			}

}
	
	cout << DistFromStart[t];
```
17行的TimeCost变量表示杂交出的种子需要的时间。
计算方式就是：生长时间+两种原材料种子的成熟时间取较晚者。
生长时间很好想，第二个取较晚者是因为必须两种原材料都要已经生成，才能开始杂交。
关于这个算法，特点就是一般需要一个struct结构体，node.id指向当前结点的编号。node.dist表示当前遍历到node结点已经走过的距离。
此外，我们还需要一个DistFromStart数组，存放的是每个种子所需要的最短时间。

最后，DistFromStart[t]存放的就是编号为t的种子的最短距离。

0.0分

1 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

徐某

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蛇行矩阵（C语言代码）

1268:P1001

【绝对值排序】（C语言代码）

迪杰斯特拉算法求最小权值

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

模拟计算器（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

矩形面积交（C++代码）

罗列完美数（C语言代码）

GC的苦恼（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

徐某

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蛇行矩阵 （C语言代码）

1268:P1001

【绝对值排序】 （C语言代码）

迪杰斯特拉算法求最小权值

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-同因查找 （C++代码）（42的倍数，，所以直接递加42输出）

模拟计算器 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

矩形面积交 （C++代码）

罗列完美数 （C语言代码）

GC的苦恼 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蛇行矩阵（C语言代码）

【绝对值排序】（C语言代码）

　　评论区

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

模拟计算器（C语言代码）

矩形面积交（C++代码）

罗列完美数（C语言代码）

GC的苦恼（C语言代码）