zcmimi's blog

arrow_back最短路共15篇文章

avatar
zc
2020-10-20 16:36:54

查看原题

点击跳转

建图比较麻烦的最短路问题

将每个城市考虑为4个机场

每个机场两两之间互相连边,若同一个城市,走高速,否则走航线

需要注意的是找出根据三个机场找出第四个机场时的分类讨论

avatar
zc
2020-10-15 22:15:41

查看原题

点击跳转

首先可以用并查集判断每个1操作是否有效

接下来很容易可以想到树剖+线段树优化建图

很可惜,出题人卡了这种大常数做法

考虑直接在树上倍增优化建图

和倍增lca差不多,一直向上连边

而每个点又拆为入点和出点

每次构建传送门时新建一个点,

连边时只需要[u_1,v_1]所在的块出点连接新建点,新建点连接[u_2,v_2]所在的块入点

详细见代码

avatar
zc
2020-09-18 14:08:00
查看原题

点击跳转

传统解法

暴力的思路是求出k个点两两之间最短路径

我们可以按二进制逐位对k个点染色(该位为1染为黑色,否则染为白色)

每次求出黑点到白点的最短距离,更新答案

这样可以保证k点中每对点 至少有一次被分别染色为黑和白

复杂度n \log n \log k

avatar
zc
2020-05-04 01:28:00
查看原题

点击跳转

容易发现,只要这个点与1之间存在某条路径长度(\le阶段数)+阶段数为偶数的,那1就得提供原材料

我们分别求出长度为奇数、偶数的最短路长度即可判断

avatar
zc
2020-01-20 07:57:00
查看原题

点击跳转

最短路松弛的比较方式变为d_x+w\le d_{to}

记得long long

avatar
zc
2020-01-19 12:25:00
查看原题

点击跳转

直接按照规则建图后跑最短路

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

先想想暴力做法:

bfs出不涉水可以到达的点,然后在这些点中找出与点1的最小距离

优化:

我们可以使用kruskal重构树来快速求出这些点

先按海拔从高到低排序,这样见出来的kruskal重构树的是海拔的小根堆

我们可以倍增找出最远可以到达的祖先,然后求出这段区间中的点与点1的最小距离

可以在dfs的时候预处理

详见代码

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

思路很妙

注意m-n \le 20

也就是说最多只有21条非树边

我们可以先跑一遍kruskal,然后按套路建树,两点之间的距离就是d_x+d_y-2\times lca(x,y)

接着剩下最多21条边(42个节点),再跑最多42次最短路就可以处理出加上非树边的结果了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

离散化 建图 最短路

烦死了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

缩点后跑最长路

1/2
Search
search