YZBPXX

图论&mdas...

acm入门练习(1) c#(1) c++，c实用小函数，操作(20) hash/bkdr hash字符串(2) 动态规划—树形dp(1) 动态规划—背包九讲(7) 单调栈(1) 图论—bfs(2) 图论—dfs(6) 图论—最小生成树(1) 字符串—ac自动机(1) 字符串—扩展KMP/KMP(4) 字符串—马拉车(1) 带权并查集(2) 拓扑排序(2) 数据库学习(6) 数据结构—RMQ(5) 数据结构—字典树(1) 数据结构--红黑二叉树(1) 数论(8) 未归档(2) 矩阵快速幂(1) 算法分析(3) 网络流(1) 集训题(2) 题解(33)

/ 注册

全部文章 / 图论—最短单源路径（共5篇）

luogu SPFA P3337

题目描述：有n个点给你m条有向边和起始点s 让你输出任一点到s的最短路分析：试着用spfa写了下注意时间复杂度是O（nv）（大于等于n*n） ac代码： #include<bits/stdc++.h> using namespace std; typedef p...

模版

2019-08-18

0 509

hdu 2544 （堆优化）

题意不在重复，对比堆优化和没优化的速度碾压优化思路在叙述一遍：整体上差别还是很大的因为堆优化用了结构体存边（模拟邻接表（但性能比不过链式前向星））而一般是用邻接矩阵存图(这个也能用邻接矩阵，不过太慢了，数据大的话还是用边吧) ，然后是就是pair自定义了大小...

模版

2019-08-18

0 525

spfa

首先dij，如何看待不能处理带负边的情况，因为dij的算法是目前到达的一定是最优的，如果有负边存在将会改变这种情况，可能之前到达时某点是最差情况但后面加个负数就变成最优了其次 spfa 因为它的算法过程是不断更新某点的最短路径估值（松弛操作）所以即使后面存在负边，也会更新前面的操作，从而得...

模版

2019-08-05

0 526

dijkstra+堆优化（优先队列）

代码写的很详细了而且精短，说说我个人的理解：首先用优先队列快速查找最小值，但考虑到原来队列中已经有的值不方便清除，所以标记每个点的first表示最短路径当一个点重复出现时只需要判断是否时我需要的就行了 #include<iostream> #include<vect...

模版

2019-08-05

0 685

Dijk入门（杭电2544题）

#include<bits/stdc++.h> using namespace std; //std::ios::sync_with_stdio(0); //std::cin.tie(0); const int INF=0x3f3f3f3f; int main(){ int n,...

模版

2019-05-09

0 703