计蒜课 16957 拓扑排序

[计蒜课](https://nanti.jisuanke.com/t/16957) 【代码】： ``` #include

using namespace std;

const int maxn = 1e5 + 10;
const int mod = 142857;
int t,n,m,k,x,u,v,w,num;
vector<pair<int,int> > G[maxn];
int inDeg[maxn], dp[maxn];
int virus[maxn];
queue q;

void topSort()
{
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) if(!inDeg[i]) q.push(i);
while(!q.empty())
{
int now = q.front();
q.pop();
for(int i=0;i<G[now].size();i++)
{
int nxt = G[now][i].first;
if(--inDeg[nxt] == 0) q.push(nxt);
dp[nxt] = max(dp[nxt], dp[now]+G[now][i].second);
}
}
}

int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(inDeg,0,sizeof(inDeg));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) G[i].clear();
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(make_pair(v,w));
inDeg[v]++;
}
topSort();
int maxx = -1;
for(int i=1; i<=n; i++) maxx = max(maxx,dp[i]);
printf("%d ",maxx);
}
}