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

520 阅读 0 评论 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 人评分

本文分类：题解列表
浏览次数：520 次浏览
发布日期：2023-04-06 19:52:13
本文链接：https://blog.dotcpp.com/a/95693

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 0 条评论

发表评论取消回复

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

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复