7-13 最短工期 (25 分)

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：

首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑任务结束里程碑工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

Impossible

#include <bits/stdc++.h>
using namespace std;
struct node {
    int task,time;
};
node v[105];
int gm[105][105]= {0};
void init() {
    for(auto i:v)
        i.task=i.time=0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    init();
    fill(gm[0],gm[0]+105*105,-1);
    int s,e,t;
    while(m--) {
        cin>>s>>e>>t;
        gm[s][e]=t;
        v[e].task++;
    }
    queue<int> q;
    for(int i=0; i<n; i++)
        if(v[i].task==0)
            q.push(i);
    while(!q.empty()) {
        int k=q.front();
        q.pop();
        for(int i=0; i<n; i++) {
            if(gm[k][i]>=0) {
                v[i].task--;
                if(v[i].time<v[k].time+gm[k][i])
                    v[i].time=v[k].time+gm[k][i];
                if(v[i].task==0)
                    q.push(i);
            }
        }
    }
    for(int i=0; i<n; i++) {
        if(v[i].task>0) {
            cout<<"Impossible";
            return 0;
        }
    }
    int res=0;
    for(int i=0; i<n; i++) {
        if(v[i].time>res)
            res=v[i].time;
    }
    cout<<res;
    return 0;
}