c++实现有n个节点的有向图节点编号为012…n-1。图中的边只有两种类型宽型和窄型并且存在自环和平行的边。Kij表示从节点i到节点j的宽型有向边。Zij表示从节点i到节点j的窄型有向边。输出数组a长度为nai表示从节点1到节点i的宽窄交替出现的最短路径的长度。不存在这样的路径则ai=-1。

思路：

首先，可以使用Dijkstra算法求出从节点1到各个节点的最短路径，得到数组d。

然后，对于每个节点i，可以考虑从节点1到节点i的路径上最后一条边的类型。如果最后一条边是宽型边，那么路径长度为d[i]。如果最后一条边是窄型边，那么路径长度为d[i]+1。因此，可以使用两个数组w和n，分别表示从节点1到节点i的最短宽型路径长度和最短窄型路径长度。

接下来，考虑如何更新数组w和n。假设当前正在处理从节点1到节点i的路径，最后一条边的类型为宽型边。那么，可以考虑从节点i出发的所有宽型边和窄型边，更新从节点1到节点j的最短宽型路径长度和最短窄型路径长度。具体地，对于每条宽型边(i, j)，如果w[i]+K[i][j]<w[j]，那么更新w[j]=w[i]+K[i][j]。对于每条窄型边(i, j)，如果n[i]+Z[i][j]<n[j]，那么更新n[j]=n[i]+Z[i][j]。最后，如果w[j]<INF（INF表示正无穷），则更新a[j]=w[j]；如果n[j]<INF，则更新a[j]=n[j]+1。如果a[j]还没有被更新过，那么说明从节点1到节点j没有宽窄交替出现的路径，因此a[j]=-1。

代码实现：

const int INF = 1e9;
vector<pair<int, int>> adj[1005]; // 邻接表，存储图
int K[1005][1005], Z[1005][1005]; // 边的权值
int d[1005], w[1005], n[1005], a[1005]; // 数组
bool vis[1005];

void dijkstra(int s) {
    fill(d, d+1005, INF);
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> K[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> Z[i][j];
        }
    }
    // 构建邻接表
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (K[i][j] < INF) {
                adj[i].push_back({j, K[i][j]});
            }
            if (Z[i][j] < INF) {
                adj[i].push_back({j, Z[i][j]});
            }
        }
    }
    // 使用Dijkstra算法求出从节点1到各个节点的最短路径
    dijkstra(0);
    // 初始化数组
    fill(w, w+1005, INF);
    fill(n, n+1005, INF);
    fill(a, a+1005, -1);
    // 更新数组w和n
    for (int u = 0; u < n; u++) {
        for (auto [v, w] : adj[u]) {
            if (d[u] + w == d[v]) { // 宽型边
                if (w < K[u][v]) { // 走窄型边更优
                    n[v] = min(n[v], w);
                } else {
                    w[v] = min(w[v], w);
                }
            } else if (d[u] + w + 1 == d[v]) { // 窄型边
                if (w < Z[u][v]) { // 走宽型边更优
                    w[v] = min(w[v], w+1);
                } else {
                    n[v] = min(n[v], w+1);
                }
            }
        }
    }
    // 更新数组a
    for (int i = 1; i < n; i++) {
        if (w[i] < INF) {
            a[i] = w[i];
        } else if (n[i] < INF) {
            a[i] = n[i] + 1;
        }
    }
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}