到最短路专辑的传送门

1001

题目大意：
计算从A到B的最短路长度。

算法：
直白的最短路，数据量比较小可以使用多种方法求解。

备注：
尝试用Dijkstra , SPFA , Bellman-Ford, Floyd等多种方法求解。
熟练图的常用表示方法：邻接表，邻接矩阵。
注意两个顶点可能有重边。

1002

题目大意：
计算从起点集S到终点集E之间的一条最短路长度。
即求一个点对(A , B), A属于S，B属于E，使得A与B之间的距离dis(A, B)<=dis(S中任意一点 , E中任意一点)。

算法：
朴素的想法是枚举每个起点，算出每个起点到终点集的最短距离，取最小值。如果有N个起点，此方法就要执行N次单源最短路。
可以引入一个新的起点newS和一个新的终点newE。新的起点连接所有S的顶点，新的重点连接E的顶点，新建的边长为0。求newS和newE之间的最短路，得到的就是期望得到的最短路+两条零边。

备注：
新建节点的思想。

1003

题目大意：
计算从A到B的最短路长度。
特别之处：顶点名由字符串给出。

算法：
比起1001的难点就是对顶点名作映射，可以有以下几种方法：
1. STL的map，很方便，速度不快，适用于顶点不多的情况。
2. 字符串hash，速度很快，但对hash冲突有一定要求，如果冲突将出错。
3. 二分查找， 先对所有字符串进行排序，那么每个字符串所在的下标就是该字符串的映射值，要寻找某字符串的映射值可以对该字符串二分。速度很快。
4. 字典树， 先对所有字符串建一棵字典树，并在字典树中每个字符串的终端节点记录该串的映射值。

备注：
尝试上述四种字符串映射方法。

1004

同1001。

1005

题目大意：
计算从顶点S到E的Be Progress的路径的条数。
Be Progress定义：He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. （如果从B到终点至少有一条路比从A到终点短，并且A->B有边，那么从A->B就是Be Progress的。）

算法：
dis[k]：从k到终点的最短路长度。
如果dis[B]<dis[A]且A->B有边, 那么就是符合条件（Be Progress）的。
可以先求出从终点到其他点的最短路（想一想，为什么不是起点？）
然后从起点进行DP，以下是类C代码：
num[st]=1
DFS( int st )
{
    for ( i = all st’s sons )   {
         if ( dis[st] > dis[ son[st][i] ] )
            num[ son[st][i] ] += num[st];
    }
    for ( i = all st’s sons )   {
        DFS( son[st][i] );
    }
}

1006

题目大意：
计算从顶点S到E的最小权值路径（即最短路）。
特殊之处：
1. 除了路径，顶点也有权值，通过某顶点，就消耗对应的权值。
2. 如果算出多条的最小权值路径，输出字典序最小的那条。

算法：
1.对于顶点也有权值的情况，可以把该权值加到所有以它为弧尾的单向边上。
2.对于字典序最小，可以在求反图的最短路的过程中，松弛时若dis[v]+l[v][u] == dis[u], 且pre[v]<pre[u]，则pre[u] = pre[v]。也就是仅在权值相等处判断字典序先后，采取自终点向起点局部贪心的策略，（想一想：从起点到终点会怎么样？）

1007

题目大意：
电梯在每i层只能上升或下降a[i]高度（不能超出1~h的建筑高度范围）。求从起点到终点要按多少次电梯按钮。

算法：
广搜或最短路。最短路的做法：对i->i+a[i] (i+a[i]<=h),i->i-a[i](i-a[i]>0)建边，后从起点到终点探索最短路。

1008

题目大意：
两两货币之间有相应的汇率，给定这些汇率后，问是否有利可图。
有利可图的情况举例：A : B = 2, B : C = 3 , C : A = 1 (A : C = 6 , C : A = 1， 则这里有利可图)

算法：
题目实质是用一个单位的A,A->B->C->…->A，一系列转化之后，能否兑换出多于一单位的A，即它们的汇率连乘是否>1。
可以用floyd做全源最长路（方法与最短路一样，松弛的时候取较大值，路径权值是乘法）。
用bellman-ford或者spfa：如果一个顶点被松弛n次则有环，表示有利可图。
字符串映射参见1003。

1009

题目大意：
计算从起点集S到顶点E之间的一条最短路长度。

算法：
参见1002

1010

题目大意：
计算从起点到多个给顶点的来回最短路径长度之和。（有向图）

算法：
朴素的算法是，对起点做一次单源最短路+对所有终点算单源最短路。
其实可以只做两次单源最短路：第一次从起点做单源最短路，第二次也是从起点开始做，不过是建了反图（所有边反向）再做。
字符串映射参见1003。

1011

题目大意：
每一条边各有一个高度限制，求从起点到终点找一条路径，使能够通过的货车高度最高。如果有多条这样的路径，输出最短的那条。

算法：
二分货车的高度h，如果高度>=h边才算合法，然后求通过合法边的最短路。

1012

题目大意：

从起点S到终点E的最短路，图比较特别，可以用广搜或最短路。

算法：
本题主要考验对输入的处理和保存，最短路部分参见1001。

1013

题目大意：
计算从A到B的最短路径长度。路径权值按照给定方法计算。

算法：
最短路部分见1001。

1014

传送门

1015

题目大意：
给定一个安全系数矩阵，要求从顶点A到顶点B的最安全路径。路径安全系数Safe(P) = s(e1)*s(e2)…*s(ek)，即所有路径的安全系数之积。
对Safe(P)取对数后，log(Safe(P)) = log(s(e1)) + log(s(e2)) … + log(s(ek))，相当于求最长路长度。（实际上直接用乘法本没错，取log是为了增加精度。）

算法：
这里不存在环，求最长路只需将松弛时改为往大的方向即可（dis[v]+l[v][u]>dis[u]则dis[u]=dis[v]+l[v][u]）。

1016

题目大意：
每条边有一定的舒适度，要求从起点A到终点B的最舒适的路。
最舒适的路：该条路上舒适度之差最小。

算法：
二分枚举舒适度的差值，依次枚举舒适度的最低点，这样得到舒适度的上下界，舒适度在上下界之间的边是合法边，再用最短路判A到B通过合法边是否连通。

1017

题目大意：

在一张连通图上寻找一点A，使这个点到给定目标点集S的最远距离最小。上图虚线上的块即给定点。

算法：
可以反过来，转化为求从目标点集S到地图上所有点最短距离的最大值。求一个最大值即可。

1018

题目大意：
每一个顶点有一个高度值，在使路径上最高和最低高度差值尽量小的前提下，找到一条最短路。

算法：
同1016，二分枚举高度差，依次枚举高度的最小值，得到高度的上下界，两端点高度在上下界之间的边事合法边，再用最短路判A到B通过合法边是否连通。

1019

题目大意：
SUM = sum{    dis(vi , vj) | 1<=i,j<=n    }
题目给出一些变长为1的边，要求输出删掉第i条(1<=i<=n)边的SUM值，如果整张图不再连通则输出INF。

算法：
边长为一，可以用广搜在O(n)时间内算出从一个点到其他点的最短距离和。
预处理原图，对图的每个顶点算出其到其他顶点的最短距离和，并记录这棵最短路径树包含的边。预处理时间O(n^2)。
对于每条边，分两种情况：
1. 如果这条边不在原图的第i个顶点的最短路径树上，删去边后对i点的最短路径树不会有影响。
2. 如果这条边在原图的第i个顶点的最短路径树上，那么要重新计算这棵最短路径树，O(n^2)。

最坏情况的复杂度是O(n*n*m)。

本题也有DP的算法：传送门。

1020

题目大意：
求最短路和比最短路长1单位的路的条数。

算法：
可以转化为求最短路的条数N和次短路的条数M，如果 次短路长==最短路长-1 ， 则答案为N+M， 否则答案为N。
次短路的算法：
最短路一定从前驱节点的最短路而来。
次短路可能从前驱节点的最短路或次短路更新而来。
这里要把数组都搞成2维的，dist[] [0]记录最短路，dist[][1]记录次短路，再搞一个cnt数组进行计数。

详细解释及代码学习：传送门。

1021

题目大意：
一张无向图上有两个人，其中一个从A走到B，另一个从C走到D，问他们两人各自都走最短路的公共点的最大值。（取最大值是因为两人的最短路都可能有多条）。

算法：
1. floyd算法：

首先证明他们的公共点一定可以是一条连续的路。
假如公共点不是连续的，如上图，分叉部分的两个路径，选一条顶点多的变成公共路径效果一定不会更差。

在floyd中，增加一个数组，num[i][j]表示从i->j的最短路上至多有多少个点。
初始化时：

松弛时：

                    if ( dis[i][j] == INF || dis[i][j] > t1)    {
                        dis[i][j] = t1;
                        num[i][j] = t2;
                    }    else if ( dis[i][j] == t1 && num[i][j] < t2 )    {
                        num[i][j] = t2;
                    }

最后枚举公共路径的两个端点，判断这条公共路径能不能作为两人的最短路径上的子路径，如果行，则取num[i][j]的最大值。

2. 单源最短路算法：
把从A到B的所有最短路构成的有向子图抠出来，再把从C到D的所有最短路构成的有向子图抠出来，最短公共路径一定在两个子图的交集上。
然后做类似最长公共子序列的dp
dp[i][j]表示从A->i的最短路径，从C->j的最短路径的最多公共点数。
i == j : dp[i][j] = dp[ pre1[i] ][ pre2[j] ]。
i !=  j : dp[i][j] = max( dp[pre1[i] ][j] , dp[ i ][ pre2[j] ]。

1022

题目大意：
求次短路的条数，特别的这题的数据中有路径长为0的情况，足以让本题变成一道难题。许多过的算法都有漏洞。

算法：
基本想法还是和1020一样求最短路和次短路条数。对于0的情况要特殊考虑。

原创文章，转载请注明： 转载自MadFroG

本文链接地址: 最短路专辑小结