Top_Sort+Floyd实现关键路径
安昙
2018-07-17 09:59:46
```cpp
#include<iostream>
using namespace std;
int n,m;
int g[5000][5000];
int in[5000];
int top[5000];
int d[5000];
void top_sort()
{
for(int i=1;i<=n;i++)
{
int k=1;
while(k<=n&&in[k]!=0)k++;
in[k]=0x7fffffff;
top[i]=k;
for(int o=1;o<=n;o++)if(g[k][o]!=0)in[o]--;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=c;
in[b]++;//b的入度++
}
top_sort();//拓扑排序
for(int i=2;i<=n;i++)
for(int o=1;o<=i-1;o++)
if(g[top[o]][top[i]]+d[top[o]]>d[top[i]])
d[top[i]]=g[top[o]][top[i]]+d[top[o]];
cout<<d[top[n]];
}
```