分层图复习 / abc325e

1234567890sjx · 2023-10-28 14:37:38 · 题解

这个题比 D 题简单多啦！

因为只能从坐车切换到坐火车，所以考虑用分层图跑最短路。

建立 G_0 和 G_1 两张图，对于一条 x\to y 的边同时加在 G_0 和 G_1 两张图上。

由于可以在任意时刻任意地点从坐车（G_0）免费不用时切换到坐火车（G_1），所以对于每一个点 i，建立一条 G_0 向 G_1，边权为 0 的有向边。

起点是 G_0 图中的 1 号点。

终点是 G_1 图中的 n 号点。

直接跑 Dijkstra 求最短路即可。时间复杂度是 O(n^2\log n^2) 的，有点卡常。

如果采用不优化的 Dijkstra 算法，时间复杂度是 O(n^2) 的，随便冲。

好奇的问一嘴：分层图不是绿的吗，为什么这个题是黄啊。