C++ 实现宽窄交替最短路径算法

问题描述：

有 n 个节点的有向图，节点编号为 0，1，2，…，n-1。图中的边只有两种类型，宽型和窄型，并且存在自环和平行的边。

K[i,j] 表示从节点 i 到节点 j 的宽型有向边。
Z[i,j] 表示从节点 i 到节点 j 的窄型有向边。

输出数组 a，长度为 n，a[i] 表示从节点 1 到节点 i 的宽窄交替出现的最短路径的长度。不存在这样的路径，则 a[i] = -1。

思路：

这道题是一道图论中的最短路径问题，我们可以使用 Dijkstra 算法来解决。但是，需要注意的是，这道题中的路径是宽窄交替出现的，也就是说，我们需要在 Dijkstra 算法基础上增加一个维度，记录当前路径是宽型还是窄型。具体来说，我们可以使用一个三元组 (u, v, w)，其中 u 表示当前节点，v 表示上一个节点，w 表示当前路径的类型（0 表示宽型，1 表示窄型），以此来记录当前路径的状态。

算法流程：

初始化：将起点加入优先队列，距离数组 dist 初始化为 INF，路径类型数组 path 初始化为 -1。
循环：从优先队列中取出距离最小的节点 u，更新与 u 相邻节点的距离和路径类型。
判断：如果找到了终点，直接返回，否则继续循环。
输出：将 dist 数组转化为 a 数组，即可得到从节点 1 到节点 i 的宽窄交替出现的最短路径的长度。

代码实现：

// ... 代码实现 ...