2、AB14 最小生成树
题目链接：最小生成树
2.1、解题思路
本题要求在最小花费下将 n 户人家连接起来，很显然是最小生成树的问题，我采用prim算法：
将二维数组cost按权升序排序，那么cost[0][2]就是最小的一个权值
将连接这条边的两个顶点放入unordered_set容器：
unordered_set 容器的元素是无序的，可以用来给顶点去重
内置的 find 方法也很好用
接下来遍历cost二维数组，直到所有顶点全部放入容器中，遍历结束
将遍历中权值的和返回，程序结束
2.2、代码实现与注释
本题源码：
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回最小的花费代价使得这n户人家连接起来 * @param n int n户人家的村庄 * @param m int m条路 * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价 * @return int */ // 自定义排序规则：按权递增 static bool cmp(vector<int>& x, vector<int>& y) { return x[2] < y[2]; } int miniSpanningTree(int n, int m, vector<vector<int> >& cost) { unordered_set<int> points; // 记录不重复的点 int res = 0; sort(cost.begin(), cost.end(), cmp); res += cost[0][2]; // 此时res 为最小权值 // 将最小边加入 points.insert(cost[0][0]); points.insert(cost[0][1]); while (1) { if (points.size() == n) break; // 所有的点连同后退出循环 // 遍历剩余的边 for (auto it = cost.begin(); it != cost.end(); it++) { // 如果边仅有一个点在集合内就加入 if ((points.find((*it)[0]) != points.end() && points.find((*it)[1]) == points.end()) || (points.find((*it)[1]) != points.end() && points.find((*it)[0]) == points.end())) { res += (*it)[2]; points.insert((*it)[0]); points.insert((*it)[1]); cost.erase(it); // 删除该边 break; } } } return res; } };
重要注释：
cmp 是自定义的一个按权递增的排序函数，配合sort函数来将cost排序
相关知识点可以参考我的博文：自定义排序规则
auto关键字可以自动推导表达式类型，在这里就相当于vector<vector<int>>::iterator
if的条件很长，但其实就是将有且仅有一个顶点在points中的边找到：
获取该边的权值并求和，将另一顶点插入到points 中
将该边删除，重新遍历cost，直到全部顶点被插入到points中
最终的 res 就是该题的结果，即最小花费。
3、AB15 单源最短路2
题目链接：单源最短路2
3.1、解题思路
使用Dijkstra算法（即不断从未处理集合中找当前距离源点最近的顶点以添加到已处理集合中，直至未处理集合为空的算法思想）
对于无向图，采用邻接矩阵表示点与点的连接关系以及距离
使用数组dist记录每个顶点与源点的距离：
本题中就是记录顶点1与其他顶点的距离
用一个布尔类型的数组记录顶点的处理情况：
初始状态全部设为false，一经处理就设为true
最终dist[n]就是顶点n到源点的最短距离
3.2、代码实现与注释
本题源码
#include<iostream> #include<climits> // 使用INT_MAX所需要引入的头文件 using namespace std; const int N = 5000; // 注意题干，图的点数是固定值5000 int main() { int G[N + 1][N + 1]; // 用于模拟邻接矩阵进行建图 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { G[i][j] = INT_MAX; // 先将邻接矩阵全部初始化为无穷大 } } int n, m; cin >> n >> m; int u, v, w; for (int i = 1; i <= m; i++) { cin >> u >> v >> w; G[u][v] = w; G[v][u] = w; // 需要关于主对角线对称，因此两边都需要存储 } int dist[N + 1]; // 用于存储每个顶点当前与源点的最短距离 bool flag[N + 1]; // 用于记录每个顶点是否已经完成与源点最短距离的计算处理 for (int i = 1; i <= N; i++) { dist[i] = G[1][i]; // 初始设置为邻接矩阵中源点所在 行 的权值 flag[i] = false; } dist[1] = 0; flag[1] = true; // 将源点加入已处理集合 for (int i = 2; i <= N; i++) { int tmp = INT_MAX, index = 1; for (int j = 1; j <= N; j++) { // 遍历寻找与源点的最短距离 if (flag[j] == false && dist[j] < tmp) { tmp = dist[j]; index = j; } } if (index != 1) { flag[index] = true; // 找到后将其加入已处理集合 } for (int j = 2; j <= N; j++) { if (flag[j] == false && G[index][j] != INT_MAX) { if (G[index][j] + dist[index] < dist[j]) { dist[j] = G[index][j] + dist[index]; // 更新最短路径 } } } } if (dist[n] != INT_MAX) { cout << dist[n]; } else { cout << -1; } return 0; }
重要注释：
二维数组G是具化出的邻接矩阵，将元素值全部初始化为无穷大：INT_MAX
u,v记录两个顶点，w记录顶点间距离，全部存入G中
dist数组用来存放各顶点到源点的距离，flag数组记录顶点是否被处理过
index代表着与源点连接且距离最短的未经处理的顶点：
随后将该顶点设为已处理
然后index寻找与之相连且未经处理的顶点：
dist[index]是index到源点的最短距离，如果加上与之相连的顶点的距离较小，那么就更新最短路径
最终的dist数组的值就是各点到源点的最短路径
