题意：

给定一个有向图，我们从顶点 $1$ 出发，想要到达顶点 $N$。

有两种操作：

1. 沿着有向边移动到下一个顶点，花费为 $1$。
2. 反转所有边的方向，花费为 $X$。

我们的目标是找到到达 $N$ 的最小总花费。

思路：

最短路，迪杰斯特拉。

只需要改建图就行了。

建图：

每个顶点 $u$ 在原图和反转图中被分别表示为两个节点 $2 \times u$ 为状态 $0$ 原图和 $2 \times u+1$ 为状态 $1$ 反转图。

原图边：对于原边 $u$ 到 $v$，在状态 $0$ 中添加边 $2 \times u$ 到 $2 \times v$ 代价为 $1$。

反转边：对于原边 $u$ 到 $v$，在状态 $1$ 中添加边 $2 \times v+1$ 到 $2 \times u+1$ 代价为 $1$。

状态切换边：每个顶点 $u$ 在两种状态间添加 $2 \times u$ 到 $2 \times u + 1$ 的双向边，代价为 $X$。

之后照常跑迪杰斯特拉就行了。

因为每个点都被分成了两个，所以最后输出要在两个终点中取最小值。

提交记录和代码。