最短路

· · 个人记录

集训小结

算法:floyed,dijkstra+堆优化,SPFA

[BZOJ 1774]过路费

一条路径的费用=每条边的权值和+各个点的权值的最大值

Floyed 性质：只用第一重循环k及它前面的点更新i,j间距，将点按点权从小到大排序，当前k点权即这条路径上除了i，j外最大点权,则dis[i][k]与dis[k][j]路径上最大点权即max(di,dj,dk)。

[LUOGU 1119] 灾后重建

村庄在ti天被重建完成后方可通车

同上，将村庄按重建时间排序，Floyed只更新到当前时间，必定不经过未修建村庄。

[POJ 3660]Cow Contest

每次给两牛关系，求最终能确定几头牛的排名

Floyed转移关系后，两两枚举，若有牛能确定n-1对关系，则其排名可确定。

[NOIP 2014] 寻找道路

路径上的所有点的出边所指向的点都直接或间接与终点连通

反向建边，第一遍bfs从终点出发标记所有可到达的点，并枚举不可到达的点删除其出边通向的点（注意这里要再开一个数组记录被删除的点，否则会影响对不可到达的点的判断），最后从终点再跑一遍bfs即可（边权均为一）。其实没有用到最短路

[LUOGU 1354]房间最短路问题 *

在一个长宽均为10，入口出口分别为(0, 5),(10, 5)的房间里有n堵 墙，每堵墙上有两个缺口，求入口到出口的最短路经。

有用的点只有每堵墙的两个端点，将这些点相连建图即可。
判断两线是否相交的方法并不明白：
判断A, B在线段C, D两侧：(AC × AD )(BC × BD ) ≤ 0 判断C, D在 线段A, B两侧：(CA × CB )(DA × DB ) ≤ 0 其中叉积符号×定义为：a × b = xayb − xbya = |a||b|sin < a, b >

[UVA 11374]Airport Express *

N个点，从起点S到终点E，有M条经济和K条商业线，只能乘坐一 次商业线，求最短时间。

枚举商业线，以s，e为起点分别跑一次最短路，记录时要用两个dis数组，输出贼恶心。
同学已经用SPFA跑过了，然而我依然改不对qaq

[BZOJ 4152][Hihocoder 1138]The Captain

给定平面上的n个点，定义(x1, y1)到(x2, y2)的费用 为min(|x1 − x2|, |y1 − y2|)，求从1号点走到n号点的最小费用。

min(a,b)+min(c,d)<=min(a+b,c+d)
只有两点之间没有其他点时，两点连线才是最优的，但这样连线仍然会存在大量无意义的边，因此我们分别按横纵坐标排序连线，跑最短路即可。

下面的题自我要求就是意会了[捂脸]

[UVA 10603]Fill *

有三个杯子它们的容量分别是三个正整数a, b, c, 并且初始状态下第 一个和第二个是空的，第三个杯子是满水的。可以把一个杯子的水倒入 另一个杯子，当然，当被倒的杯子满了或者倒的杯子水完了，就不能继 续倒了。
你的任务是写一个程序计算出用最少的倒水量，使得其中一个杯子 里有d升水。如果不能倒出d升水的话，那么找到一个d0 < d ，使得d0最接近d。

思想还是比较好理解的：将每个状态看作一个点，边权即转移水的数量，最短路走一发即可，同时可以利用三者和为c强行降一维。但是代码emmm

[BZOJ 2143]飞飞侠

一个N × M的矩形方阵，每个格子代表一个街区，对于第i行第j列 的街区，使用有Aij的费用就可以弹跳到距离不超过Bij 的街区。告诉你 三个人的坐标，需要前往其中的某个人那里集合，问到哪一个人那儿的 总费用最低。

非常巧妙的一道题.假设弹跳距离bij就是弹跳点的高度h,可以向五个方向与比它低一层的点连边,即有 f[i][j][h] -> f[i][j][h-1] , f[i-1][j][h-1] , f[i][j-1][h-1] , f[i+1][j][h-1] , f[i][j+1][h-1],边的权值为0.会发现h为0时正好处于弹跳点的跳跃边界上,并且在弹跳范围内不花费额外费用,与题目要求契合.再在每一点都向正上方连一条权值为a[i][j]的边,到达高为b[i][j]的点,从三个起点分别跑dij即可.

[NOIP 2013]华容道 *

操作关键在于指定块的位置,而指定块只会随空白块移动而移动,用(x1,y1,dir)表示指定块在(x1,y1),空白块在其dir位置时的状态,可以很好的节省空间.关于操作有5种:1.交换空白块与指定块的位置,边权为1;2.将空白块通过若干步操作移动到指定块的上/下/左/右,边权通过bfs等可得.像这样先将空白块移到指定块旁边,之后向目标状态跑最短路.

[BZOJ 2118]墨墨的等式 *

已知{an}, Bmin, Bmax问有多少组解满足a1x1 + a2x2 + · · · + anxn = B，其中B 的取值范围为[Bmin, Bmax ]

p=min(ai),令d[i]表示当物体的总重mod p = i时，物体最少的重量,则所有x mod p = i的数均可由d[i]加上若干p得到，并且 d[(i+u) mod p] 可由 d[i]+u 转移，求d[i]的最小值就与最短路的思想相近。
其实还是比较蒙

[BZOJ 3875]骑士游戏

给定n个怪物，每个怪物可以用魔法直接干掉，或者用物理攻击使其分裂为一些其他怪物，普通攻击需要消耗si的体力，法术攻击需要消耗ki的体力，同时i号怪兽死亡后会产生ri个新的怪兽。求杀掉1号怪物的最小花销。