最短路
https://codeforces.com/contest/1076/problem/D 题目大意 给出 $n \ (2 \le n \le 3 \times 10 ^ 5)$ 个点 $m \ (n - 1 \le m \le 3 \times 10^5)$ 条边的无向连通图。问最多保留 $k \ (0 \le k \le m)$ 条边时，最多可以使多少点的从 $1$ 点出发的最短路长度不变，输出任意最好方案下保留边的集合。 简要题解 显
…
https://codeforces.com/contest/1922/problem/C 题目大意 给出数轴上的 $n \ (2 \le n \le 10^5)$ 个点。$0 \le a_1 < a_2 < a_3 < \cdots < a_n \le 10^9$ 从 $i$ 点直接走到另外一个点 $j$ 的花费为 $|a_i - a_j|$ 或当 $j$ 是 $i$ 与所有点之间距离最近的点时花费为 $1$。 给出 $m \ (1 \le m \le 10^5)$ 次询问。每次问从 $x_i$ 到 $y_i$
…
https://codeforces.com/contest/1202/problem/B 题目大意 给出一个 $0 \sim 9$ 字符组成的序列 $S \ (1 \le |S| \le 2 \times 10^6)$ 且 $S$ 总以 $0$ 开始，这个序列是由 $x, y \ (0 \le x, y \le 9)$ 由以下规则生成出来的。 最初数字 $a$ 为 $0$。输出这个数 随机的从 $x, y$ 中选出一个数加到 $a$ 上并输出 $a$ 的个位
…
约翰逊 Johnson 算法 全源最短路 对于最短路问题，我们的常用算法是 Dijkstra 算法或 Bellman-Ford 算法。但这两个算法经常解决的是单源最短路问题。 对于多源（全源）最短路问题，我们有一个基于动态规划的优秀算法，Floyd-Warshall
…
弗洛伊德 Floyd // T must define < and + template<typename T,size_t V,bool Directed=true,T INF=T(0x3f3f3f3f)> struct Floyd { T g[V][V]; int n; void init(int n_) { n=n_; for(int i=0;i<n;i++) for(int j=0;j<n;j++) g[i][j]=INF; } void addedge(int u,int v,T w) // check multi-edges { g[u][v]=w; if(!Directed) g[v][u]=w; } void cmin(T &x,const T &y) { if(y<x) x=y; } void floyd(Upd =upd) { for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) cmin(g[i][j],g[i][k]+g[k][j]); } };
…
迪杰斯特拉 Dijkstra 模板（priority_queue） // T must define < and + // V: max number of vertex [0~V-1] template<typename T,size_t V,bool Directed=true, T INF=T(0x3f3f3f3f),T ZERO=T(0)> struct G { typedef pair<T,int> PTI; vector<PTI> g[V]; T dis[V]; int vis[V]; int n; void init(int n_) { n=n_; for(int i=0;i<n;i++) g[i].clear(); } void addedge(int u,int v,T w) { g[u].emplace_back(w,v); if(!Directed) g[v].emplace_back(w,u); } void dijkstra(int st,int ed=-1) // ed=-1 no destination { for(int i=0;i<n;i++) dis[i]=INF,vis[i]=0; priority_queue<PTI,vector<PTI>,greater<PTI> > qu; dis[st]=ZERO; qu.emplace(ZERO,st); while(!qu.empty()) { PTI p=qu.top(); qu.pop();
…