注:

• 使用栈或者队列都可以实现
• early_start[N]:任务最早开始时间
• last_start[N]:任务最晚开始时间
• 图必须无环

当
$$\color{#FF2E63}{\boxed{\mathrm{\color{Red}{early\_start[i]==last\_start[i]}}}}$$
1. 说明该任务为$\color{#57D1C9}{关键任务}$，不能早也不能晚
2. 关键事件之间的边称为$\color{#ff8a5c}{关键活动}$，所有的关键活动构成$\color{#fd5f00}{关键路径}$

AOE图。。。懒得画了太难画了√

in:

9 11
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 6
4 6 8
4 7 7
5 7 4
6 8 2
7 8 4

out:

0 6 4 5 7 11 15 15 19 
0 7 7 5 8 11 17 15 19 

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;
const int N = 100010;
int h[N],e[N],ne[N],w[N],idx;
int early_start[N],last_start[N],d[N];
stack<int> s1;
stack<int> s2;
int n,m;

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}

bool topsort()
{
    stack<int> s1;
    for(int i = 0;i < n;i ++)
        if(!d[i]) s1.push(i);

    while(!s1.empty())
    {
        int u=s1.top();s1.pop();s2.push(u);
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            early_start[j] = max(early_start[j],early_start[u] + w[i]);
            if(-- d[j] == 0) s1.push(j);
        }
    }
    return s2.size() == n;
}

void invtopsort()
{
    for(int i = 0;i < n;i ++) last_start[i] = early_start[n - 1];

    while(!s2.empty())
    {
        int u = s2.top();s2.pop();
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            last_start[u] = min(last_start[u],last_start[j] - w[i]);
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i ++)
    {
        int a,b,c;cin >> a >> b >> c;
        add(a,b,c);
        d[b] ++;
    }

    if(topsort())
    {
        invtopsort();
        for(int i = 0;i <n ;i ++) cout << early_start[i] << " ";
        puts("");
        for(int i = 0;i < n;i ++) cout << last_start[i] << " ";
    }

    return 0;
}