分层图复习 / abc325e

这个题比 `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)$ 的，随便冲。 好奇的问一嘴：分层图不是绿的吗，为什么这个题是黄啊。