单/多源最短路的三种算法 — dijkstra & spfa & floyd

什么是最短路

单源最短路：计算图中一个点到其他各点的最短距离
多源最短路：计算图中多个点到其他各点的最短距离

单源最短路 — dijkstra 算法

算法描述

main 函数：用vector数组存边，初始化一维数组 dist 来表示起点到其他各点的距离（到自己为 0，其他点为 INF），将初始边（目标点为起点，权值为 0）加入到优先队列 queue 中
dijkstra 函数：抛出优先队列的 top 边，若这个边的权值比现在到这个目标点的权值大（说明起点到该点的长度又更新了，而且那个边肯定在这个边前面），就跳过，否则就疏松以这个点为起点的所有边，若通过这个点，起始点到其他的点的距离有减小的，则把路径减小的目标点和减小后的距离加入到优先队列中，重复操作

最小生成树的两种算法 — Prim & Kruscal

什么是最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 {\displaystyle (u,v)\in E}(u,v)\in E），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且 (V, T) 为树，使得 w(T) 最小，则此 T 为 G 的最小生成树。

题目：互不侵犯

题目描述

在 N*N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。

题目：Magry的朋友很多 - 零食篇

题目描述

Magry有个好朋友Ricardo快要过生日了。Ricardo突然想到可以借生日坑蒙拐骗点东西出来，于是就找了Magry要他买零食当生日礼物。

Magry手上没那么多钱，不过想了想还是上了天猫超市搜了一波，被那么多吃的看的眼花缭乱头晕目眩不知所措，因为Ricardo只有一个要求，那就是东西尽量好吃，而且还不要有Ricardo不喜欢的东西。。。

Magry已经知道的是：卖的零食总共有n种，不过比较坑爹的是一种零食一个用户限购一件；每种商品的价格为x元，好吃程度为w。另外，Magry已经知道在那些零食中有一部分是Ricardo不喜欢的（也许是忌口，总之这个和零食的好吃程度毫无关联，甚至对于一部分好吃程度为0甚至是负数的黑暗料理Ricardo也很有可能喜欢吃）。然后，Magry身上总共只有k元。

现在，Magry想要的是：如何确定购买方案使得在Magry手上的k元不会被透支（即商品总额不大于k元）的情况下买到总的好吃程度最高并且没有Ricardo不喜欢的零食呢？

欢迎大家来到我的博客，在下在写博客这方面是一个新人小白，如果有人来看的话，希望不要笑话我O(∩_∩)O

我在博客中会写的东西

编程学习过程的笔记

因为我的编程技术很菜，而且脑子又不好，学了啥都记不住，所以想在我的博客中记录下我学习的东西，以便我在以后的时候通过看我的博客能够快速回顾，如果有人能看到我的博客，也希望能从我的笔记中有一些收获，如果我的笔记能对更多人有帮助的话，我会感到十分荣幸