关注
求问D为什么建返图就会WA,建正图才能AC。 正图代码 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int maxm=200000+5;
const int INF=0x3f3f3f3f;
const ll mod=20010905;
int n,m;
int head[maxn],tot=1;
int in[maxn];
ll d[maxn];
queue<int>q;
struct node{
int from,to,c;
}edge[maxm];
void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void dp(){
d[1]=1;
q.push(1);
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
d[y]=(d[y]+d[x])%mod;
if(--in[y]==0){
q.push(y);
}
}
}
printf("%lld",d[n]%mod);
}
int main() {
// ios::sync_with_stdio(false); freopen("DDoS.in","r",stdin);
scanf("%d%d",&n,&m);
int from,to,c;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&from,&to,&c);
add(from,to);
in[to]++;
}
dp();
return 0;
} 反图代码 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int maxm=200000+5;
const int INF=0x3f3f3f3f;
const ll mod=20010905;
int n,m;
int head[maxn],tot=1;
int in[maxn];
ll d[maxn];
queue<int>q;
struct node{
int from,to,c;
}edge[maxm];
void add(int from,int to){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
void dp(){
d[n]=1;
q.push(n);
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
d[y]=(d[y]+d[x])%mod;
if(--in[y]==0){
q.push(y);
}
}
}
printf("%lld",d[1]%mod);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("DDoS.in","r",stdin);
scanf("%d%d",&n,&m);
int from,to,c;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&from,&to,&c);
add(to,from); //反图
in[from]++;
}
dp();
return 0;
}
查看原帖
1 评论
相关推荐
06-19 14:10
西南财经大学 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
66831次浏览 593人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92102次浏览 679人参与
# 秋招签约后的心态变化 #
82549次浏览 814人参与
# 听劝,这个公司值得去吗 #
486188次浏览 1700人参与
# 你觉得早上几点上班合适? #
72392次浏览 303人参与
# 学历贬值真的很严重吗? #
24497次浏览 174人参与
# 机械人与华为的爱恨情仇 #
120173次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186499次浏览 1859人参与
# 打工人的工作餐日常 #
53258次浏览 415人参与
# 哪些公司真双非友好? #
15840次浏览 82人参与
# 26届的你们有几段实习? #
44140次浏览 488人参与
# 月薪多少能在一线城市生存 #
28192次浏览 305人参与
# 双非能在秋招上岸吗? #
221742次浏览 1172人参与
# 你以为的实习VS真实的实习 #
29851次浏览 274人参与
# 今年秋招哪家公司给的薪资最良心? #
252964次浏览 1418人参与
# 你后悔自己读研吗? #
20652次浏览 240人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
117939次浏览 812人参与
# 追觅科技求职进展汇总 #
18269次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
149960次浏览 932人参与
# 如何KTV领导 #
62802次浏览 472人参与