【拾题杂谈】最短路计数
题面：最短路计数大秦为你打开题目传送门
题目描述给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。
输入格式第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。
接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条连接顶点 $x$ 和顶点 $y$ 的边，请注意可能有自环与重边。
输出格式共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。
样例 #1样例输入 #1123456785 71 21 32 43 42 34 54 5
样例输出 #11234511124
提示$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。
对于 $20\%$ 的数据 ...
【拾题杂谈】[USACO06NOV] Roadblocks G
题面：[USACO06NOV] Roadblocks G大秦为你打开题目传送门
题面翻译贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。贝茜所在的乡村有 $R(1\le R \le 10^5)$ 条双向道路，每条路都联结了所有的 $N(1\le N\le 5000)$ 个农场中的某两个。贝茜居住在农场 $1$，她的朋友们居住在农场 $N$（即贝茜每次旅行的目的地）。贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
题目描述Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old hom ...
【拾题杂谈】[USACO07FEB] Cow Party S
题面：[USACO07FEB] Cow Party S大秦为你打开题目传送门
题目描述寒假到了，$n$ 头牛都要去参加一场在编号为 $x$ 的牛的农场举行的派对，农场之间有 $m$ 条有向路，每条路都有一定的长度。
每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 $n$ 头牛的最短路径（一个来回）中最长的一条路径长度。
输入格式第一行有三个整数，分别表示牛的数量 $n$，道路数 $m$ 和派对农场编号 $x$。接下来 $m$ 行，每行三个整数 $u, v, w$，表示存在一条由 $u$ 通向 $v$ 的长度为 $w$ 的道路。
输出格式输出一行一个整数表示答案。
样例 #1样例输入 #11234567894 8 21 2 41 3 21 4 72 1 12 3 53 1 23 4 44 2 3
样例输出 #1110
提示样例 1 解释
数据规模与约定对于全部的测试点，保证 $1 \leq x \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq u,v \leq n$，$1 \leq w \leq 10^2 ...
【拾题杂谈】POJ1734 Sightseeing trip
题面题目链接大秦 为你打开 题目传送门
题目翻译找出带权无向图图上至少有三个的最小环，若无解，输出 No Solution. ，图的节点数不超过 $100$ ，边数不超过 $10000$ ，每条边的权值小于等于 $500$ 且大于 $0$ 。
思路这个数据范围一眼顶针就是 Floyd 算法，但是我们如何去求最小环就变成了问题。我们考虑一个环是如何组成的（前提是环的一部分是最短路）见下图：
这样是一个环的组成部分，那么就可以用这个思路，去得到最小环的权值，但是问题现在又来了，如何得到环上的点。我们发现 Floyd 每次在进行松弛操作会有一个中转点，我们记录这个中转点，不断还原出原路径即可。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021 ...
【算法介绍】最短路算法
算法简介：晶片也是一种宝石这篇文章主要讲的是最短路径算法，从最低级的 Floyd 开始，到支持最长路的 Dijskra 的初级代码及其优化，还有支持负边权的 Bellman-Ford 算法。最短路径问题作为图论中解决大多数问题的基础，可以与很多图论模型混搭，是一个泛用型很强的问题类型。
算法演示：不能少了冲天转转例一：改良型平衡稳定器首先，作为多个最短路算法的始祖（可能吧，毕竟这个是基础）一些关于最短路的基础概念都是由 Floyd 算法引导出来的，所以我们首先来讲的算法，就是 Floyd 算法。
首先，我们给定一张图。不管他是无向图还是有向图，我们都可以求最短路。而计算出来的最短路，分为两种：
求出一个点到所有点之间的最短路 —— 单源最短路
求出所有点到所有点之间的最短路 —— 全源最短路
那么我们要用的 Floyd 算法，就是求全源最短路的一个最短路算法。试想一下，如果要求我们在 $O(n^3)$ 的时间复杂度内，实现全源最短路，我们会怎么做？不难想到，就是动态规划。
如果我们设置一个状态 $dp[u][v]$ 表示点 $u$ 到 $v$ 的最短路，那么怎么去求最短路呢？ 不难 ...
【拾题杂谈】LuoguP2619 [国家集训队] Tree I
题面：[国家集训队] Tree I题目链接大秦为你打开题目传送门
题目描述给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $need$ 条白色边的生成树。
题目保证有解。
输入格式第一行 $V,E,need$ 分别表示点数，边数和需要的白色边数。
接下来 $E$ 行，每行 $s,t,c,col$ 表示这边的端点（点从 $0$ 开始标号），边权，颜色（$0$ 白色 $1$ 黑色）。
输出格式一行，表示所求生成树的边权和。
样例 #1样例输入 #11232 2 10 1 1 10 1 2 0
样例输出 #112
提示对于 $5\%$ 的数据，$V\leq 10$。
对于另 $15\%$ 的数据，$V\leq 15$。
对于 $100\%$ 的数据，$V\leq 5\times10^4,E\leq 10^5$。
所有数据边权为 $[1,100]$ 中的正整数。
By WJMZBMR
思路首先，要达到最小生成树固定颜色边的目的，最首要的部分就是控制权重。但是发现如果单一的规定白色边或者黑色边排在前面，满足不了一定是 need 条白色边的需求，所以不难想到枚举给白色边的加 ...
【算法介绍】最小生成树
算法简介：割舍怜悯之心最小生成树，就是一张图一直删边，直到删成一颗树为止，这叫做生成树，如果这个生成树的边权之和是所有生成树中最小的，那么他被称为最小生成树，前面我们讲过了一个叫做 Boruvka 的算法，虽然他确实是求最小生成树的方法之一，但是他过于远古，不太常用，代码也不如 kruskal 简单，所以说，我们这里将介绍两种新的最小生成树算法，请看副标题 —— Prim & kruskal 。
算法演示：割舍侥幸之心那么最小生成树，生成树生成树，总归就是树，有两种组成部分，一是点，二是边，而 Prim 和 kruskal 算法分别就是代表了基于点的贪心和基于边的贪心，我们来一个逐个击破。
点贪心：割舍痛苦之心首先就是 Prim 算法，他之所以被称为点贪心，是因为这样一个思路：
生成树，必须要把一个图的所有点连起来，变成一个树，也就是说，所有点，我们都将出现在最终的点集合里。所以，我们一开始随便选择一个点，加入最小生成树点集合，然后每次去寻找和我们最小生成树点集合最近的一个点，这样就可以保证每次选出来的边是最短的，然后就一直循环往复，直到所有点都选完。
然后，我们就发现，这样的 ...
【算法介绍】线段树合并
算法简介：悬星尽散击云碎一般来讲，我们在大值域的权值线段树问题的时候，都会考虑把它变成离线的，然后进行线段树操作。但是，以万恶的出题人视角，一定会把这唯一的路给断掉，也就是强制在线的大值域权值线段树问题，那么我们就要考虑到动态开点权值线段树了。至于动态开点线段树的应用……想必都知道了吧 —— 线段树合并。
算法演示：璇玑合璧镇昆仑第一部分：星罗宿列天权临那么既然要讲的是动态开点权值线段树的应用，自然要讲动态开点权值线段树。那么我们首先来想，动态开点权值线段树的内存理论应该是多少。首先我们想权值线段树的内存，就和普通线段树一样，都是开了 $4N$ 的，那么如果是动态开点，显而易见我们就可以达到线段树的理论内存，$N\log V$ 其中，$N$ 是数据范围，$V$ 是值域。
有人可能想不通：我们都不知道数据里面最大的那个数，怎么开始数组，怎么建树，怎么往下递归寻找答案？
上面这个有人是谁，我也不知道，但是有没有一种可能，我们是动态开点，我们不需要建树，我们的内存就是 $N\log V$ ，内存直接开到这么大就够了，也就是一般来讲的 N<<5 。这个 $5$ 的出处是 $2^ ...
【算法介绍】KMP算法
算法简介：巡护深林KMP 算法，虽然我们已经在 【算法介绍】字符串算法 | 祝馀宫 中提及，但是现在有了更深的理解，我们这篇文章单独讲 KMP 算法以及其原理。为了凑字数，我们再讲一遍废话。 KMP 算法，全称 $Knuth-Morris-Pratt$ 算法，通过一种特殊的性质匹配两个字符串，从而达到减少匹配次数的算法。
算法演示：漫行山薮变量定义：夏堇芳菲我们对于接下来的一些内容做出如下定义：
名称
定义
子串
不用多说了罢，在字符串中截取任意一段连续的内容，被称为子串下文用 $s[l\dots r]$ 表示字符串 $s$ 的从 $l$ 到 $r$ 的这部分子串。 下文所有关于字符串的计算都是以 1 为开始的下标*
子序列
不要求连续，但是在原字符串中内容顺序相同的字符串。
前缀子串
一个字符串的前缀组成的子串，表示为 $pre(s,i)=s[1\dots i]$ ，即 $s$ 字符串长度为 $i$ 的前缀
后缀子串
一个字符串的后缀组成的子串，表示为 $suf(s, i) = s[n-i+1\dots n]$ ，即 $s$ 字符串长度为 $i$ 的后缀
...
【拾题杂谈】LuoguP4159 [SCOI2009] 迷路
题面：[SCOI2009] 迷路大秦为你打开题目传送门
题目背景windy 在有向图中迷路了。
题目描述该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。
现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？
答案对 $2009$ 取模。
注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
输入格式第一行包含两个整数，分别代表 $n$ 和 $t$。
第 $2$ 到第 $(n + 1)$ 行，每行一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $c_{i, j}$ 是一个数字字符，若为 $0$，则代表节点 $i$ 到节点 $j$ 无边，否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i, j}$。
输出格式输出一行一个整数代表答案对 $2009$ 取模的结果。
样例 #1样例输入 #11232 21100
样例输出 #111
样例 #2样例输入 #21234565 3012045071054780512024123 ...
