题目,我调了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;
}
希望这次不会在被团队内的同学发现(