yizimi远欣

题解

其他(14) 算法及模板(3) 课内(2)

/ 注册

全部文章 / 题解（共6篇）

题解 P4779 【【模板】单源最短路径（标准版）】

既然卡SPFA，那就用Dijkstra + 堆优化我太菜了就不会SPFA 就是要注意，可能有些同学会说： “我们又不是不会Dijkstra + 堆优化” 于是自信满满的交上，一看就傻眼了，，， 60分？！ #2 #3 TLE？！这里就是一个需要注意的地方了 ...

Dijkstra 最短路

2018-12-02

0 430

题解 P1339 【[USACO09OCT]热浪Heat Wave】

不会SPFA的同学们看过来既然dalao们都在打SPFA，我也不会SPFA，所以写个Dijkstra的题解。首先提醒那些和我一样感觉自己的代码对，刚从P3371 【模板】单源最短路径（弱化版）过来的同学。这个题的边是无向图！！！听到大佬说是模板题，我就从P3371直接...

Dijkstra 最短路

2018-12-02

0 460

题解 P1186 【玛丽卡】

见大佬们都是用的SPFA 为了关心Dijkstra党，所以这里写一篇关于Dijkstra的题解主要思路：这个题意实在是太模糊了，我也是听了大佬的解释才明白的。我可以再次翻译一遍题意QAQ：找出在一条边断掉的情况下的单源最短路径，并输出最坏的情况（去边不同会影响最...

Dijkstra 最短路

2018-12-02

0 511

题解 P1339 【[USACO09OCT]热浪Heat Wave】——线段树做法

Dijkstra + 线段树解法最近集训一位大佬给我讲了一个奇妙的Dijkstra优化方法，他告诉我线段树可以代替优先队列来优化Dijkstra。我第一个感觉是眼睛一亮于是我认真的听完了他讲的方法。 Dijkstra算法周围的大佬已经讲的十分的漂亮了，我觉得我再插一嘴就...

Dijkstra 最短路线段树

2018-12-02

0 380

题解 P2296 【寻找道路】

主要思路：DFS + Dijkstra + 堆优化 + 反向思维要不是写代码的时间问题我就用线段树优化了首先，题目要求是路径上的所有点的出边所指向的点都直接或间接与终点连通。我们可以先不考虑如何通过某点到达终点，我们想象如果通过一个点可以再到达终点，说明把边反过来后，终点可以...

Dijkstra 最短路

2018-12-02

0 445

【题解】PAT 1003 Emergency

主要思路：Dijkstra + DP 如果做过最短路计数，这道题就相当于双倍经验了。就是在跑Dijkstra时，另计一个 \(t_i\) 作为到第 \(i\) 个点时最短路的条数，一个 \(rs_i\) 作为到第 \(i\) 个点最短路点权和的最大值注意一下维护条数时要分类，是...

DP 最短路 Dijkstra

2019-12-10

0 616