最短路
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();
…