{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/1d8jrjht %}
题意： #
给定一个有向图，我们从顶点 $1$ 出发，想要到达顶点 $N$。
有两种操作：
- 沿着有向边移动到下一个顶点，花费为 $1$。
- 反转所有边的方向，花费为 $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$。
之后照常跑迪杰斯特拉就行了。
因为每个点都被分成了两个，所以最后输出要在两个终点中取最小值。