最短路
（一）Dijkstra
Dijkstra算法可求任一点到定点的最短路，适于有向图和无向图（对有向图有用的就一定对无向图有用），其边权不可为负（一条边都不行）。数组vis标记访问过的点，数组dis记录结果，一般初始化为无穷。dis[起点]要提前赋值，以保证在for循环中第一个目标点是起点。
对于稀疏图（即边的数量E远小于n*(n-1)），Dijkstra算法可以优化至(V+E)logV，称为堆优化。具体就是用优先队列，直接弹出待选结点中d[x]最小的点。普通二叉堆优化后的复杂度为O((V+E)logV)，而若使用斐波那契堆，由于压入操作为O(1)，可将复杂度优化至O(E+VlogV)（但是过程复杂，比赛中不使用）。在稀疏图中，使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；而在稠密图中，这时候使用暴力\(O(n^2)\)做法较二叉堆实现更优。
当边权均为一常数时，可用bfs搜寻；当边权为0和1时，可用双端队列+bfs搜寻。如果要还原路径，这时需要引入父点数组。由于除了起点外每个点都有唯一的父结点，这时所有路径便形成了一棵树，称最短路径树。在这棵树上，根节点到任意结点的路径最短。
当存在多个起点时（即多源最短路），可设置一“超级源点”，通过边权为0的边连接所有起点，则图上任一点到最近源点的距离即为到超级源点的距离，“超级汇点”同理。当某些点能通过特殊方式走到其他任何点时，可让它连接到一个虚点，这个虚点再连接到图中所有点。
在某一点到源点的路径长度最短的前提下，处理一些二级条件，我们需要在dis[to]==dis[index]+G[index][to]时：①使得路径上的点权和最小：当wg[to]>wg[index]+w[to]时更新wg[to]和fa[to]。（如果希望是希望点权和最小时使路径最短，那么我们把一二级条件互换即可）②使得路径上的最大点权最小：当wg[to]>max(wg[index],w[to])时更新wg[to]和fa[to]（与①不同，②的一二级条件不可互换）。③统计最短路数量：tot[to]+=tot[index]。④使得路径上的额外边权和最小：参考①即可。
if(dis[to]>=dis[now]+w)
{
if(dis[to]>dis[now]+w)
{
dis[to]=dis[now]+w;
wg[to]=wg[now]+w[to]; //wg[x]为1~x的路径点权和
fa[to]=now; //fa[x]为x在最短路径树上的父节点
}
else if(wg[to]>wg[index]+w[to])
{
wg[to]=wg[now]+w[to];
fa[to]=now;
}
}
一些最优路径问题并不是简单的权和最短，Dijkstra可以描述为在未标记的点中找到最优点，将其标记后优化其相邻点，这种优化/松弛是单调的，就像边权一样只可非负，以确保被已标记的点不可能再被优化更新。比如说，假设边权点权均为正数时，求1到任一点i的路径的最大的“最小点权/路径长度”、最小的“路径最大值最小值之差”等，这些值在点与点转移时，必然始终增加或减少（也就是转移边权恒大于0或小于0，具体值可以未知），而当边权恒正时求最小、边权恒负时求最大，我们就可以采用Dijkstra算法；若需边权可正求最大、边权可负求最小，则要用到spfa。
有向图中的最小环问题：枚举s=1-n，更新s所有的出边所连接的点v，设置dis[v]为边权，然后正常地跑一遍dijkstra，dis[s]就是经过s的最小环。
dijkstra算法的核心在于三角不等式\(dis[to]≤dis[now]+w\)，基于此，以下将介绍几种拓展应用。
差分约束
差分约束系统是一种特殊的N元一次不等式组。它包含N个变量\(X_1\)~\(X_N\)以及M个约束条件，每个约束条件都是由两个变量作差构成的，形如\(x_i\;-x_j\;≤c_k\),其中\(c_k\)是常数(可以是非负数，也可以是负数)，1≤i, j≤N,1≤k≤M。我们要解决的问题就是：求一组解\(x_1=a_1,x_2=a_2,…,x_N= a_N\)，使所有约束条件都得到满足。
差分约束系统的每个约束条件\(x_i\;-x_j\;≤c_k\)，可以变形为\(x_i\;≤c_k\;+x_j\)，这与单源最短路径问题中的三角形不等式dist[y] ≤dist[x]+z非常相似。因此，可以把每个变量\(x_i\)看作有向图中的一个节点 i , 对于每个约束条件\(x_i\;-x_j\;≤c_k\)，从节点 j 向节点 i 连一条长度为Ck的有向边。
注意到如果{a1,a2, … ,an} 是一组解，那么对任意的常数△，{a1+△,a2+△, … ,an+△}也是一组解。这样如果我们想把一组含负数的解转换为正整数解，那么令上式中△为|最小的负数-1|即可。我们还可以设置一个虚点\(x_0=0\)并增设约束条件\(x_i\;-x_0\;>0\)，从而达到控制所有解的下限。如果差分约束系统中存在有向环，
不等号的方向可以自由选择，这要根据在具体问题中，求最短路还是求最长路更适合我们。注意不能在存在负边权的图中使用dijkstra算法求最短路（等价于不能在存在正边权的图中求最长路），也最好不要在非稀疏图中使用SPFA算法。另外，所求得的一组解只是针对一个连通块（底图连通，不含虚点）而言的，如果不止一个连通块，我们需要对每组解独立处理。
若\(x_i-x_j≥k\)表示\(x_i\)比\(x_j\)至少多 k ，\(x_i-x_j≤k\)表示\(x_i\)比\(x_j\)至少少 k 。我们将不等号统一方向，作由 j 向 i 的权值为k的有向边，如果差分约束系统中存在有向环，设环上边权和为 S，当求最短路时必须 S≥0，当求最长路时必须 S≤0。这意味着在非负边权图中，强连通分量对最长路的贡献只能为0，我们可以将图变成DAG图。
我们设\(x_i\)为0~i的前缀和，重点注意隐藏的约束条件。对于i>j，\(x_i-x_j >=0\)，且\(x_j+1>=x_i\)。
同余最短路
同余最短路常用于解决这样一类问题：
有n个正整数\(a_1,a_2,a_3,⋯ ,a_n\)，设\(x_1a_1+x_2a_2+…+x_na_n=k（x_1,x_2..x_n∈N）\) 。即 使用无限个\(a_1,a_2,a_3,⋯ ,a_n\)进行拼凑，然后对k的可能值进行各种询问（例如询问k在[ l , r ]区间内的可能值个数；询问k最大的无法拼凑的值；询问某个定值k能否被拼凑出……）（类似于超大完全背包）
算法思路
取其中一个正整数作为剩余系，例如取\(a_1\)，设\(f(i)=min\{k|k \% a_1=i\}\)，其中\(i=0,1,2..a_1-1\)，\(f(i)\)即为令\(k=x_2a_2+x_3a_3+…+x_na_n\)且\(k \% a_1 =i\)的最小的k。（虽然少了一项\(x_1a_1\)，但有和没有是一样的）（通俗点讲，就是选任意数量的\(a_2到a_n\)，凑成k使得\(k\%a_1=i\)，\(f(i)\)即这个最小的k。如果这个k不存在，则\(f(i)=inf\)）。
由定义易知：\(f((i+a_j)\%a_1)=min\{f(i)+a_j\}\)。其中\(f(0)=0\)。我们发现这可以转换为最短路的更新方程：$$f((i+a_j)%a_1)<=f(i)+a_j$$。
建图：显然共\(V=a_1\)个节点（从0到\(a_1-1\)），每个节点均有n条边，利用堆优化Dijkstra算法求最短路时间复杂度为\(O(nVlogV)\)。若n个正整数有重复值，则最好要去重，且为了使节点数更少，我们应当取最小的\(a_i\)作为剩余系。
求出所有的\(f(i)\)后：
（1）所有可拼凑出的值的集合即为\(\{k|f(i)+t\cdot a_1,t∈N\}\)。由简单的数论知识可知，当\(i,t\)不同时，k唯一。若限制k<h，则可由n个正整数组成的所有不同数的总量为\(\sum_{i=0}^{a_1-1}f(i)/a_1+1\)，其中\(f(i)!=inf\)且\(f(i)<=h\)。（+1的情况是指d[i]本身，也就是一个a1都不取）
for(int i=0;i<P;++i) //P=a1
{
if(d[i]!=inf && d[i]<=h)
res+=(h-d[i])/P+1;
}
（2）最大的无法拼凑出的值为\(\max\{k|k = f(i)-a_1\}\)，若为−1则表示所有值均可拼凑出来（仅当\(a_1=1\)时），若为\(inf-a_1\)则表示不可拼凑出来的数有无穷个。例如有三个整数4,3,4，我们排序去重后取\(a_1=3\)，则\(f(0)=0,f(1)=4,f(2)=8\)，最大的不可拼凑的数即为\(f(2)-3=5\)。
//求最大
sum=0;
for(int i=0;i<t;i++) sum=max(sum,d[i]-P);//P系数为1
//求最小
sum=inf;
for(int i=0;i<t;i++) sum=min(sum,d[i]-(d[i]/P)*P);//P系数为d[i]/P
（3）对于一个定值k，若需要知道其具体的拼凑方案，则还需记录最短路的具体路径。
（4）判断一个数 x 能不能由\(a_1,a_2,a_3,⋯ ,a_n\)组成，因为 f 中存的是最小值，如果\(x>=f[x\%a_1]\)，则一定能保证x由\(f[x\%a_1]\)加上若干\(a_1\)得到，否则说明k=x无解。
遥远的旅途 (51nod.com) 图上超大完全背包
假设一条从0到n-1的路径长度为a，任取一条连接n-1的无向边，w为其长度，如果题目所述的长度恰好为T的路径存在，那么一定可以表示成：\(T=a+k*2w\;\;(k∈N)\)，即\(T\%2w=a\%2w\)。若k为0表示不需要在此边上重复走。理解这个“一定”：不管路径a走得多么复杂，我们只关心它对于2w的余数，这对所有a都是唯一的。
于是取P=2w为剩余系，设b为从起点到 i 的某一路径长度，我们令\(dp[i][j]\)表示使得b%P=j的最小的b，状态之间通过连接两点的无向边转移。初始化dp[0][0]=0，跑一遍Dijkstra就能处理出dp[n-1][0~p-1]。在点n-1上，若\(T>=dp[n-1][T\%P]\)，说明 T 一定可以由记录在\(dp[n-1][T\%P]\)上的路径a加上若干2w得到。
如此，我们使用了同余模型来优化极大的数据范围。这里之所以选取连接n-1的边，是因为一定可以保证这条边接入所有路径，所以按这来分析的话，我们还可以选连接起点0的一条边作为剩余系。
（二）Floyd
Floyd算法是解决任意两点间的最短路径的一种算法，是一种插点算法，可以正确处理有向图或带负权非回路的最短路径算法 同时也被用于计算有向图的传递闭包 Floyd时间复杂度为\(O(N^3)\) ，复杂度为\(O(N^2)\)。
状态表示 ： \(f[k][i][j]\)表示所有从i出发，最终走到j，只允许经过结点1到k的所有路径的最小值
阶段划分 ： 节点编号k的不同
转移方程 ： \(f[k][i][j] = min(f[k][i][j], f[k – 1][i][k] + f[k – 1][k][j])\)
初值\(f[0][i][j]\)为原图的邻接矩阵。
\(f[k][i][j]\)可以从\(f[k-1][i][j]\)转移来，表示i到j不经过k这个节点，也可以从\(f[k-1][i][k]+f[k-1][k][j]\)转移过来，表示经过k这个点。意思即\(f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])\)。通过滚动数组思想，我们约掉了第一维，进而表示成如今的Floyd。
（k作为第一维阶段状态，这也是它必须放在最外的原因）
任意两点最短路
Floyd可求任意两点间的最短路，代码简单，允许边权为负（但不能存在权和为负的环），可以作图的预处理。k, i, j都是对所有点的枚举，且第一个for为对k枚举。记录结果的二维数组d初始化为无穷大，若i,j有边，则设置d[i][j]和dis[j][i]为边长。memset(d,0x3f,sizeof(d))可使每个元素被初始化为1061109567（0x3f3f3f3f…），属于1e9级数，两个0x3f相加恰好比int_max小一点，因此是初始化“无穷大”的不错选择（多次调用Floyd时，最好摒弃这种做法）。注意，不要在两个0x3f3f3f3f相加后再加数值，可能会造成溢出。
使用一个path数组来记录i到j经过的某个中间点，也就是说，当d[i][j]>d[i][k]+d[k][j]时，设置path[i][j]=k，然后采用分治递归，便可还原路径。注意，在有多条等长路径时，若采用“>”，所记录路径经过的顶点/边最少；若采用“≥”，所记录路径经过的顶点/边最多。如果两点p,q在i到j所记录的最短路径上，那么p到q的路径也一定记录在这条路径中。还可以设置path[i][j]为自i向j出发的下一个点，初始化path[i][j]=j（对无向图还需初始化path[j][i]=i），当dis[i][j]>dis[i][k]+dis[k][j]时，设置path[i][j]=path[i][k]，打印时循环输出即可。
void func(int a,int b)
{
if(!pt[a][b])
return;
func(pt[a][b],b);
cout<<pt[a][b])<<" ";
func(a,pt[a][b]);
}
对于点比较多的稀疏图，一个直观的想法就是，对每个点执行一次Dijkstra算法来求出任意两点最短路，复杂度为O(nmlogn)，然而Dijkstra算法不能处理含负边权的图。1977年，Donald B.Johnson提出了对所有的边权进行”re-weight”的算法，使得所有边权非负进而可以使用Dijkstra算法进行最短路的计算。
最小环问题
由上述可知，当外层的 k 刚循环到点 t 时，点t一定只存在于所有当前记录的path的端点上，而不出现在任何path的途中，也就是说，当前所有\(dis[i][j]\)表示由i向j出发不经过点集t~n的最短路。此时\(dis[i][j]+dis[i][k]+dis[k][j]\)构成了一个经过i,j,k的最小环，因此可在floyd的过程中求出(无向图)最小环。
传递闭包
在交际网络中，给定若干个元素和若干对二元关系，且关系具有传递性。我们可以使用邻接矩阵来表示变量间的关系，比如说当\(g[i][j]=true\)代表 i 和 j 有关系，然后，我们可以使用Floyd算法解决传递闭包问题。
for(k)
for(i)
for(j)
g[i][j]|=g[i][k]&g[k][j];
再比如说当\(g[i][j]=true\)代表 i<j ，这时我们有：
矛盾: g[i][j]==1&&g[j][i]==1 => a>b && b>a
不能确定大小： g[i][j]==0&&g[j][i]==0 => a?b && b?a
如果一个描述大小关系的传递闭包中没有矛盾和歧义，那么总会呈现例如这种形式：
// A B C D
//A 0 1 1 1
//B 0 0 1 0
//C 0 0 0 0
//D 0 1 1 0
可见每一行的1的数量都不相同，假设元素x所在行的1的数量为k，那么在将所有元素按从大到小的顺序排列后，x就排在第k个，且整个顺序是一定确定的。
我们可以再进一步用 bitset 优化，复杂度可以到\(O(n^3/32)\)
// std::bitset<SIZE> g[SIZE];
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (g[i][k]) g[i] = g[i] | g[k]; //表示g[i]可以继承g[k]的所有关系
矩阵快速幂
（数学水平不足，待更新）345. 牛站
点权排序
我们已经知道，当外层的k刚循环到t时，点t一定只存在于当前所有所记录的最短路径的端点上（注意只是当前的最短路径，不是最终）。点的遍历顺序并不影响Floyd算法，于是，如果将点1~n按点权大小进行排序，那么在所有最终最短路径的生成过程中，一定能保证路径最大/最小点权的单调性。详细地讲，对固定的两点\(i,j\)，其当前最短路径\(f[k][i][j]\)的最大/最小点权一定只来自w[i],w[j],w[k]，其中w[i], w[j]是常数，故而路径点权最值是单调变化的。
既然保证了点权最值单调，那么就可以维护一些与点权和边权都相关的值。比如说：
（1）求任意指定的两点路径中，最大点权不超过k的最短路径。点权排序后，任意两点的最短路径在生成过程中，最大点权递增而最短路径递减，我们可以把所有询问，按k的大小排序，在Floyd算法的过程中顺便解决，或者开二维map[N][N]，用mp[i][j][w]记录当\(i,j\)的路径最大点权为w时的最短路径，这样在每次最短路更新时，\(w=max(w[i],w[j],w[k])\)，直接设置\(mp[i][j][w]=d[i][j]\)即可。注意一开始如果\(i,j\)有边，要么初始化mp[i][j]，或者在更新值时采用“≥”。
（2）求任意指定的两点路径中，最大点权乘以最大边权的最小值。对于固定的两点\(i,j\)，在最短路径生成的过程中，为了使乘积最小，当最大点权递增时，我们更新最大边权的最小值（相当于剔除掉最大边权跟着递增的没有贡献意义的部分），这样就使得路径\(i,j\)在此过程中最大点权递增而最大边权递减，每次更新时维护最小乘积res[i][j]即可。注意一开始如果\(i,j\)有边，要么初始化res[i][j]，或者在更新值时采用“≥”。
（三）Bellman-Ford
Bellman-Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。它的代码实现极为简单——对所有的边松弛n-1次。
for(k = 1; k <= n - 1; k++)
for(i = 1; i <= m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
dis[v[i]] = dis[u[i]] + w[i];
此后可再对所有边尝试一次松弛，倘若成功松弛了某条边，说明存在负环。
负环的定义是：一条边权之和为负数的回路。最短路下的负环和最长路下的正环都会导致问题无解。另外，对于涉及“环上绝对值最小”的问题（如01分数规划），也可以考虑对负环性质的运用。
SPFA
很多时候我们并不需要那么多无用的松弛操作。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。这种优化手段（在国内）被称作SPFA算法。
必须说明的是，SPFA算法虽然跑得更快，但其最坏情况下的时间复杂度为O(nm)，没有负权边时最好使用 Dijkstra 算法。在有负权边且题目中的图没有特殊性质时，若 SPFA 是标算的一部分，题目不应当给出 Bellman-Ford 算法无法通过的数据范围。
关于SPFA的两种优化：
- LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
- SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
我们可以把LLL和SLF结合到一起：
int vis[maxn],dis[maxn];
vector<pair<int,int> > G[maxn]; //邻接表
void spfa(int st)
{
deque<int> q;
q.push_back(st);
dis[st]=0;
long long sum=0,num=1;
while(!q.empty())
{
int t=q.front();
while(dis[t]*num>sum) //LLL优化
{
q.pop_front();
q.push_back(t);
t=q.front();
}
vis[t]=0;
q.pop_front();
--num;
sum-=dis[t];
for(auto i:G[t])
{
if(dis[i.first]>dis[t]+i.second)
{
dis[i.first]=dis[t]+i.second;
if(!vis[i.first])
{
if(!q.empty() && dis[i.first]>dis[q.front()]) //SLF优化
q.push_back(i.first);
else
q.push_front(i.first);
++num;
sum+=dis[i.first];
vis[i.first]=1;
}
}
}
}
}
其他优化手段：spfa的魔改方法 – ETO组织成员 – 博客园 (cnblogs.com)
SPFA可以通过两种方式来判断负环：（1）一个点是否入队达到n次（2）起点到某点的最短路径边数是否达到n。需要注意的是，以S点为源点跑 SPFA 算法时，如果没有给出存在负环的结果，只能说明从S点出发不能抵达一个负环，而不能说明图上不存在负环。因此如果需要判断整个图上是否存在负环，最严谨的做法是执行 Bellman-Ford 算法，或者建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行SPFA算法。
虽然是介绍SPFA的章节，但我们却要着重地讨论“如何不用SPFA”。考虑在哪些情况下，可以绕开SPFA解决含负边权的最短路问题。
SCC缩点
众所周知，将有向图中的强连通分量（SCC）缩点后，便将图转换为了有向无环图。在DAG上，无论进行拓扑排序+DP还是记忆化搜索，都有十分理想的时间复杂度。如果一个强连通分量对所有穿过它的图上路径的贡献是确定的，我们就能将其缩为DAG上的一点。此类问题一般允许经过重复点。
P3387 缩点 SCC对经过它的路径的贡献，就是每个SCC中的点权总和。
题意描述：一幅由有向边和无向边构成的图，其中无向边权为正数，有向边权可负，保证任何环中都不含有向边，求从起点S到任一点的最短路。
如果我们将所有的无向边连通块缩成一个点（把有向边视作断开作dfs即可，用不到Tarjan），那么这个图就变成了一个DAG。此时我们就可以对这个图进行拓扑排序了，然后再根据拓扑序进行递推，最终就可以求出到达每个点的最短路径。由于无向边权为正，每个缩点内部的最短路我们可以直接用dijkstra算出。
（直到起点在某次djjkstra算法从堆中被弹出前，所有点的dis值都是inf。）
NOIP2009 提高组] 最优贸易 尽管这道题的正解是双向SPFA，但我们有更多时间复杂度更优秀的解法。
只需分别求出起点到任一点的最大路径点权和终点到任一点的最小路径点权即可，然而这两者都无法采用djjkstra算法得出（根据定义仔细想想）。缩为DAG后，比如在求路径最大点权时，每个SCC的贡献就是自身的最大点权。
在DAG图中找最长路，我们可以在拓扑排序后，遍历每个点，沿着其出边松弛其他点的dp值，或者更直观地，我们建立反图，从各个终点进行记忆化搜索，（建立反图是因为记忆化搜索自底向上，更适合表示 i 到 n 的最长路），复杂度为边数。
值得一提的是，所有路径规划算法本质都是在图上进行动态规划，每种算法有对应的状态转移方程（dis数组实际就是起到dp数组的作用），并利用边进行状态转移。不过动态规划问题一般都是基于DAG图（即无后效性），当存在环且不是负环时（换句话说，不会出现沿着一个环一直刷小/刷大状态值），用spfa算法一遍遍地沿每条边松弛，就能得到每个点的dp值。例如在“通信线路”中，设dp[i][p]表示从1到i的路径第p大的边的最小值，则对于权值为z的边x->y，有\(dp[y][p]=min(max(dp[x][p],z) ,dp[x][p-1])\),显然沿着一个环（边权为正）不会使dp[y][p]一直减小（包括无向边的来回），因此可以使用SPFA算法。
（四）分层图
基础运用——
分层图是指有很多个平行的图，各个平行的图之间有特殊的连接边。分层图只是建图时有区别，但诸如跑最短路板子都是一样的，只要有合适的建图方法，那么问题就很简单了。
为了更好地配合dijkstra等算法，一般的建图方式是把第x（0~k-1）层的i点表示为\(i+x*n\)，其中最后一层\(（i+k*n）\)为终点层或虚层。分层图的点数近似kn，边数近似km，以此来计算时间复杂度。
for(int i=1;i<=m;++i)
{
int x,y,z;//有向边的起点、终点、边权
cin>>x>>y>>z;
for(int j=0;j<=k;++j)//在每一层图上建立相同的边
{
G[x+j*n].push_back({y+j*n,z});
G[y+j*n].push_back({x+j*n,z});
}
}
分层图的几种使用场景：
1、 有k套不同边集建立在同一点集上，允许在某点消耗代价切换到另一边集上移动。有多种情况。
小雨坐地铁 (nowcoder.com) 换乘问题。可以将每个集合内的边建成一张图，再建立第k+1个图，是一个虚层，这个虚层的i点作为中转站，连接了前面k层所有的i点（双向边，指向虚层的边权为0），从而不需要去把每一层的同一点两两连边。如果任意一层图的某一位点\(i\)，切换到第\(t\)层的\(i_t\)需消耗x，可令虚层指向\(i_t\)的边权为x。这样任意层图就可以通过虚层转移到另一层图中。
Rinne Loves Dynamic Graph (nowcoder.com) 边权变化具有周期性，为每套边权建立分层图。
Problem – 7145 (hdu.edu.cn) 入边的不同，决定了每个点接下来的出边。此题的有向图中如果由A型边到一点，接下来可走A/B型边，如果由B型边到一点，接下来只能走A型边，我们建立两层图，第一层的点只接受A型入边，第二层的点只接受B型入边。（但是我不太理解这道题的时间复杂度）
2、 有k个机会使得走当前此边不花费代价或花费特殊的代价，可以建立k张相同的该图，对于边i-j，让上一层的i指向下一层的j，其代价是0或是特殊的值。每向下走一层，就代表用了一次机会，使得当前的路花费为0，最多可以走k次（注意如果这k次不必用完的话，每一层的终点可能更新答案）。如JLOI2011] 飞行路线
3、 有k个机会逆向走动，我们可以建k张相同的该图，将每层图之间有边的两个点用的逆向的边连接。每向下走一层，就代表用了一次机会逆向走了一次，最多可以走k次。
分层图与动态规划——
建立k+1张分层图，每一层图完全相同。称第0层的起点为始祖源点，第t层的所有点都代表了从祖源点到这里要多走t距离。
设dp[i]为从祖源点到任意层\(i\)点的路径数，我们的目标就是统计\(dp[n]+ dp[n+n]+…+dp[n+kn]\)。
在正式开始前，设dis[i]为i到n的最短路，我们建立反图，做一次dijkstra算法。1≤i≤n，dis[i]是一个全局量，跟在哪层无关。
假设现在在第0层，设连接\(x\)到\(y\)的有向边边长\(w\)，若\(dis[y]-dis[x]<w\)，说明沿此边多走了\(c=w-(dis[y]-dis[x])\)，于是我们断开本层x-y，建立一条从\(x\)到\(y+c*n\)的有向边（也不必物理断开，只要强制优先向下走就行了）。把第0层换作第t层也一样，我们建立一条从\(x\)到\(y+(t+c)*n\)的有向边。
现在，我们从祖源点出发沿着有向边自由走动，以任一层的n为终点。显然，路径上不会出现环（成环之前一定会向下移动，0环除外）。也就是说这些自由移动的路径形成了有向无环图，我们可以进行记忆化搜索或拓扑排序DP。例如对记忆化搜索而言，总复杂度为\(O(KM)\)。没有必要用SPFA进行DAG动态规划。
本题还需要对零环进行判断。事先说明，前面之所以选用i到n的最短路，是因为所有合法路径的终点是n，如果dis[i]=inf，说明走到i就到不了终点了，因此我们不向i移动（选用1到i的最短路也可以正确转移状态，但是会在不合法的路上浪费时间）。至于0环，我们在记忆化搜索时标记正处在递归状态中的节点，如果dfs到一个还未退出递归的节点，说明“DAG图”上出现了环，这个环一定是所求的零环。
还有一个问题，我们真的需要建立这K+1层图吗？注意到每层图的边集完全相同，因此我们用\(dp[k][i]\)来表达第k层的i点，在原始图上进行动态规划。
有了这种分层图DP的思想后，看待很多在有向图（有环）上的动态规划时，就不难以理解了。
340. 通信线路 – AcWing题库 （尝试用动态规划）
原文地址：http://www.cnblogs.com/blover/p/16815952.html
