书上还写了计算最晚开始时间的代码,这题里用不上,计算最早开始时间就行。

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

using namespace std;

const int N = 1001;
const int INF=INT_MAX;

struct edge{
    int to;
    int length;
    edge(int a, int b): to(a), length(b) {}
};

int n, m;
vector<edge> graph[N];
int indegree[N];
int nodelist[N];
int earlist[N];//最早开始时间

void func(int n){
    //priority_queue<int, vector<int>, greater<int> > node; //存入度为0的点 
    queue<int> node;
    for(int i = 0; i < n; i++){
        if(indegree[i] == 0){
            node.push(i);
            earlist[i] = 1;
        }
    }
    int num = 0;
    while(!node.empty()){
        int u = node.front();
        nodelist[num++] = u;
        node.pop();
        for(int i = 0; i < graph[u].size(); i++){
            int v = graph[u][i].to;
            int l = graph[u][i].length;
            earlist[v] = max(earlist[v], earlist[u] + l);
            indegree[v]--;    //后续节点入度-1     
            if(indegree[v] == 0){
                node.push(v);
            }
        } 
    }    
}

int main(){
    int from, to, cost;
    while(cin >> n >> m){
        memset(graph, 0, sizeof(graph)); 
        memset(indegree, 0, sizeof(indegree));
        memset(earlist, 0, sizeof(earlist));
        while(m--){
            cin >> from >> to >> cost;
            graph[from].push_back(edge(to, cost)); 
            indegree[to]++;
        }    
        func(n);
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans = max(ans, earlist[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}