PTA 5-12 How Long Does It Take (25分)

这题看不太懂题目啊~  参考的http://blog.****.net/qq_26437925/article/details/49420089?locationNum=6&fps=1

先放着吧。

#include  "iostream"
#include "vector"
using namespace std;
int in_degree[]; /* 记录图的各个节点的入度 */
struct Node {
    int e;
    int cost;
};
vector<Node>v[];
int early[];
int n, m;
bool toplogicSort() {
    int start = -;
    for (int i = ; i < n; i++) {
        if (in_degree[i] == ) {
            start = i;
            break;
        }
    }
    if (start == -) { /* 没有入度为0的点 完不成项目*/
        return false;
    }
    early[start] = ;
    int sum = ;
    int num = ;
    int newP = start;
    while (num != n - ) {
        int len = v[newP].size(); /* 出度 */
        for (int i = ; i < len; i++) {
            int e = v[newP][i].e;
            int cost = v[newP][i].cost;
            in_degree[e]--;
            if (early[newP] + cost > early[e]) {
                early[e] = early[newP] + cost;
            }
        }
        in_degree[newP] = -; /* 删除该节点 */
        newP = -;
        for (int i = ; i < n; i++) {
            if (in_degree[i] == ) {
                newP = i;
                break;
            }
        }
        if (newP == -)
            return false;
        if (early[newP] > sum)
            sum = early[newP];
        num++;
    }
    cout << sum << endl;
    return true;
}
int main() {
    Node node;
    cin >> n >> m;
    for(int i = ; i < n; i++){
    in_degree[i] = ;
    early[i] = ;
    }
    while (m--) {
        int s, e, l;
        cin >> s >> e >> l;
        node.e = e;
        node.cost = l;
        v[s].push_back(node);
        in_degree[e]++;
    }
    if (!toplogicSort())
        cout << "Impossible" << endl;
}