Dijkstra算法   Dijkstra算法算是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。   问题引入: 指定一个点(源点)到其余各个顶点的最短路径,也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。         &n…

2021年5月4日 0条评论 8点热度 阅读全文

还有八九十天就NOIP了,我还是要复习一下最短路这类关键的知识点. 原来认为dijkstra堆优化和spfa会一个就行,spfa时间优,码长短.但是近几年spfa不考了.(总是被出题人D)。故意构造数据可以卡到O(k*n^2),有可能跑不过裸dij,所以今天的内容是dijkstra的堆优化,但不会dijkstra也没关系,我现在讲一下. dijkstra是一个单源最短路.起点固定来求. 我们设起点为S.dis[i]表示由S到达i的最短路径. 那么我们可以从S点开始枚举.运用蓝白点的思维.先把S标志为蓝点表示它已经是…

2021年5月4日 0条评论 22点热度 阅读全文

#include <vector> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <iostream> using namespace std; #define N 100010 #define LL long long #define inf 0x7f7f7f7f #define mem(a,n) memset(a,n,sizeo…

2019年2月11日 0条评论 15点热度 阅读全文

首先,何为最短路? 假设有五个点,每个点之间都有一条连线,并且赋予距离。给予一对起点与终点,让你求出从起点到终点的最短距离,或者最短时间。   HDU2544. 这个问题可以枚举,从1-2,1-3,1-2-3等等并求出其最短的路线,但是如果数据太多怎么办。假如有1000个点,挨个枚举可能会枚举半年,所以这个时候引出几种算法,我们先来看第一种。以下算法我们都以一道题为例题:输入N,M(分别表示终点N,并且有M条边),接下来输入M行x,y,z分别表示从点x到点y的距离为z,求出1-N的最短距离,例如 2 3 …

2019年1月23日 0条评论 15点热度 阅读全文

主要是为了方便自己忘记的时候复习一遍, 不适合初学者 全部内容摘自他人博客     spfa: 上图来自此处   dijkstra:       上图来自此处     算法思路对比 Dijkstra+heap是用小根堆,每次取出d最小的点,来更新距离,那么这个点来说,最小距离就是当前的d。 SPFA是用双端队列,每次取出队头,来更新距离,它之后可能还会入队。它是一种动态逼近法,因为每次松弛距离都会减小,所以松弛一定会有结束的。如果一个点…

2019年1月21日 0条评论 16点热度 阅读全文

文章目录 Description Input Output 4种做法 勾股定理 1.Floyed-Warshall算法O(N^3) Floyed-Warshall代码 2.Dijkstra算法O(N^2) Dijkstra代码 3.Bellman-Ford算法O(NE) Bellman-Ford代码 4.SPFA算法O(kE) Description 平面上有n个点(N<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通…

2019年1月18日 0条评论 10点热度 阅读全文

文章目录 Description Input Output 4种做法 勾股定理 1.Floyed-Warshall算法O(N^3) Floyed-Warshall代码 2.Dijkstra算法O(N^2) Dijkstra代码 3.Bellman-Ford算法O(NE) Bellman-Ford代码 4.SPFA算法O(kE) Description 平面上有n个点(N<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通…

2019年1月18日 0条评论 9点热度 阅读全文

在下边的学习中,主要是学习指定一个点(源点)到其余的各个顶点的最短路径,也叫做“单源最短路径”。 例如下图中的1号顶点到2,3,4,5,6顶点的最短路径: 在这里要和flody算法一样,在这儿也需要用二维数组e来存取顶点之间和边之间的关系,数值如下: 在这儿我们还需要用一个一维数组dis来存取1号顶点到各个顶点的初始路程,如下: 因为dis中存取的是各个顶点到1号顶点的初始距离,所以我们把dis数组中的值称为最短路的“估计值”。   既然我们是求1号顶点到其余各个顶点的最短路程,那我们就可以先找一个距离1…

2019年1月16日 0条评论 13点热度 阅读全文

https://nanti.jisuanke.com/t/10772 在嘟嘟生活的王国有 n 座城市,某些城市之间有传输电能的线路。在某条线路传输电能是会有损耗的,某一个城市在某一时间只可以向另外一个城市传输电能。已知在城市 s 存在 m 千瓦时电能,求将这些电能都传输到城市 t ,至少需要损耗多少电能。   输入格式 输入包含多组测试数据,对于每组测试数据: 第一行包含一个整数 n ( 0 < n ≤ 50000 ) 。 接下来输入包含 n 部分,对于第 i ( 1 ≤ i ≤ n )部分:第一行…

2018年12月21日 0条评论 26点热度 阅读全文

Buy a Ticket Musicians of a popular band “Flayer” have announced that they are going to “make their exit” with a world tour. Of course, they will visit Berland as well. There are n cities in Berland. People can travel between cities using two-directional train…

2018年11月23日 0条评论 9点热度 阅读全文