求助T122157
查看原帖
求助T122157
572482
Dream_weavers楼主2022/1/27 10:21

题目,我调了114514遍了,不是40就是20,用拓扑排序做的QAQ,code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int n,m,s,t,cnt,inde[N],dp[N];
vector<int> adj[N];
priority_queue<int,vector<int>,greater<int> >q;
void topsort(){
	for(int i=1;i<=n;i++)
		if(inde[i]==0)
		    q.push(i),dp[i]=1;
	while(!q.empty()){
		int u=q.top();
		q.pop();
		for(int i=0;i<adj[u].size();i++){
			int v=adj[u][i];
			inde[v]--;
			dp[v]+=dp[u];
			if(inde[v]==0){
				q.push(v); 
			} 
		}
	}
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		adj[u].push_back(v);
		inde[v]++;
	}
	topsort();
	if(dp[t])printf("%lld",dp[t]);
	else printf("No Path!");
    return 0;
}

希望这次不会在被团队内的同学发现(

2022/1/27 10:21
加载中...