本文主要是介绍最短工期-拓扑排序模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。（项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。）
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,deg[N],d[N],vs[N];
struct nd{int v,w;
};
vector<nd> e[N];int main() {cin>>n>>m;for(int i=1;i<=m;i++) {int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});deg[v]++;}queue<int> q;for(int i=0;i<n;i++)if(deg[i]==0) q.push(i),vs[i]=1;while(!q.empty()) {int u=q.front();q.pop();for(int i=0;i<e[u].size();i++) {nd to=e[u][i];deg[to.v]--;if(!deg[to.v]) vs[to.v]=1,q.push(to.v);d[to.v]=max(d[to.v],d[u]+to.w);}}for(int i=0;i<n;i++) {if(!vs[i]) {cout<<"Impossible"<<endl;return 0;}}int ans=0;for(int i=0;i<n;i++) ans=max(ans,d[i]);cout<<ans<<endl;return 0;
}
这篇关于最短工期-拓扑排序模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
