悬赏 2 个关注

md 调了好长时间，一直 TLE：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=1e6+5;
int n,m,ss;
vector<pair<long,long> > G[N],g[N];
long long dfn[N],low[N],in_stack[N],scc[N],val[N],dp[N];
stack<int> s;
long long cnt,ll;
void Tarjan(int u){
	dfn[u]=low[u]=++cnt;
	s.push(u);
	in_stack[u]=1;
	for(auto [v,va]:G[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(in_stack[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}if(dfn[u]==low[u]){
		++ll;
		while(s.top()!=u){
			in_stack[s.top()]=0;
			scc[s.top()]=ll;
			s.pop();
		}
		in_stack[s.top()]=0;
		s.pop();
		scc[u]=ll;
	}
	return ;
}
void dfs(int u){
    if(dp[u]!=-1) return;
    dp[u]=0;
    for(auto [v,w]:g[u]) dfs(v),dp[u]=max(dp[u],dp[v]+w);
    dp[u]+=val[u];
}
signed main(){
    n=read();
    m=read();
	int u,v,w;
	while(m--){
	    u=read();
	    v=read();
	    w=read();
		G[u].push_back({v,w});
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
		    Tarjan(i);
		}
	}
	ss=read();
	for(int u=1;u<=n;++u){
		for(auto [i,va]:G[u]){
			if(scc[i]!=scc[u]){
				g[scc[u]].push_back({scc[i],va});
			}else{
				int qaz=0;
				while(va>=0){
					val[scc[u]]+=va;
					++qaz;
					va-=qaz;
				}
			}
		}
	}
	for(int i=0;i<=ll;++i) dp[i]=-1;
	dfs(scc[ss]);
	printf("%lld",dp[scc[ss]]);
	return 0;
}