书上还写了计算最晚开始时间的代码,这题里用不上,计算最早开始时间就行。
#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; }