c++给定有向无环网的顶点数、弧数、弧的信息，输出各关键路径上活动信息。X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2 dut表示弧尾、弧头及权值），数据之间由空格分隔；X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2 dut表示弧尾、弧头及权值），数据之间由空格分隔；

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, w, nxt;
} e[MAXN * MAXN];

int head[MAXN], ecnt = 1;
int indegree[MAXN], topo[MAXN], cnt = 0;
int n, m, s, t;
int earliest[MAXN], latest[MAXN], ve[MAXN], vl[MAXN], path[MAXN];

void add_edge(int u, int v, int w) {
    e[++ecnt].to = v;
    e[ecnt].w = w;
    e[ecnt].nxt = head[u];
    head[u] = ecnt;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
            earliest[i] = 0;
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo[++cnt] = u;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            int w = e[i].w;
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
            earliest[v] = max(earliest[v], earliest[u] + w);
        }
    }
}

void dfs(int u) {
    if (u == t) return;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        int w = e[i].w;
        if (vl[v] - w == vl[u]) {
            path[++path[0]] = i;
            dfs(v);
            break;
        }
    }
}

int main() {
    while (cin >> n >> m) {
        memset(head, 0, sizeof(head));
        memset(indegree, 0, sizeof(indegree));
        ecnt = 1;
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, w);
            indegree[v]++;
        }
        topsort();
        s = topo[1], t = topo[cnt];
        for (int i = 1; i <= n; ++i) {
            latest[i] = INF;
            vl[i] = earliest[t];
        }
        for (int i = cnt; i >= 1; --i) {
            int u = topo[i];
            for (int j = head[u]; j; j = e[j].nxt) {
                int v = e[j].to;
                int w = e[j].w;
                latest[u] = min(latest[u], latest[v] - w);
            }
            vl[u] = min(vl[u], latest[u]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = head[i]; j; j = e[j].nxt) {
                int v = e[j].to;
                int w = e[j].w;
                if (earliest[i] + w == earliest[v]) {
                    ve[v] = earliest[v] - w;
                }
            }
        }
        dfs(s);
        cout << "关键路径: ";
        for (int i = 1; i <= path[0]; ++i) {
            cout << path[i] << " ";
        }
        cout << endl;
        cout << "活动最早开始时间: ";
        for (int i = 1; i <= n; ++i) {
            cout << ve[i] << " ";
        }
        cout << endl;
        cout << "活动最晚开始时间: ";
        for (int i = 1; i <= n; ++i) {
            cout << vl[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

注：由于输入格式不明确，此代码实现中假设输入的有向无环图是连通的，即任意两个顶点之间都有一条路径。如果输入的有向无环图不连通，则需要对每个连通分量进行拓扑排序和动态规划。