C++ 实现有向图宽窄交替最短路径

思路：

采用动态规划的思想，设 dp[i][0/1] 为从节点 1 到节点 i 最后一条边是宽型/窄型的最短路径长度。

对于每个节点 i，有两种情况：

1. 最后一条边是宽型，那么 dp[i][0] = min{dp[j][1] + K[j][i]}，其中 j 为 i 的前驱节点。
2. 最后一条边是窄型，那么 dp[i][1] = min{dp[j][0] + Z[j][i]}，其中 j 为 i 的前驱节点。

最后答案数组 a[i] = min(dp[i][0], dp[i][1])。

代码实现：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int main() {
  int n, m, k, z;
  cin >> n >> m >> k >> z;

  // 初始化宽型边和窄型边矩阵
  vector<vector<int>> K(n, vector<int>(n, numeric_limits<int>::max()));
  vector<vector<int>> Z(n, vector<int>(n, numeric_limits<int>::max()));

  // 输入宽型边和窄型边信息
  for (int i = 0; i < k; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    K[u][v] = w;
  }
  for (int i = 0; i < z; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    Z[u][v] = w;
  }

  // 初始化dp数组
  vector<vector<int>> dp(n, vector<int>(2, numeric_limits<int>::max()));
  dp[1][0] = 0;  // 从节点1到节点1的宽型边路径长度为0
  dp[1][1] = 0;  // 从节点1到节点1的窄型边路径长度为0

  // 动态规划计算最短路径长度
  for (int i = 2; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (K[j][i] != numeric_limits<int>::max()) {
        dp[i][0] = min(dp[i][0], dp[j][1] + K[j][i]);
      }
      if (Z[j][i] != numeric_limits<int>::max()) {
        dp[i][1] = min(dp[i][1], dp[j][0] + Z[j][i]);
      }
    }
  }

  // 输出答案数组
  vector<int> a(n, -1);
  for (int i = 1; i < n; i++) {
    a[i] = min(dp[i][0], dp[i][1]);
  }
  for (int i = 1; i < n; i++) {
    cout << a[i] << ' ';
  }
  cout << endl;

  return 0;
}