关注
求问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 评论
相关推荐
投递星环科技等公司10个岗位 >
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
569796次浏览 9529人参与
# 简历中的项目经历要怎么写 #
407441次浏览 6799人参与
# 如何写一份好简历 #
240189次浏览 3689人参与
# 平台or薪资 硬件uu更看重哪个 #
22453次浏览 147人参与
# 我的上岸简历长这样 #
150994次浏览 3028人参与
# 你的简历改到第几版了 #
285409次浏览 4359人参与
# 远程面试的尴尬瞬间 #
3111次浏览 71人参与
# 春招你拿到offer了吗 #
344198次浏览 5142人参与
# 海康威视求职进展汇总 #
85546次浏览 1048人参与
# 我的成功项目解析 #
77186次浏览 2282人参与
# 现在还是0offer,延毕还是备考 #
343266次浏览 4415人参与
# 你已经投递多少份简历了 #
273538次浏览 4191人参与
# 我的失利项目复盘 #
199404次浏览 4396人参与
# 你觉得比亚迪今年还有春招吗? #
41223次浏览 296人参与
# 浅聊一下我实习的辛苦费 #
75961次浏览 707人参与
# 晒一晒我的offer #
3096039次浏览 52096人参与
# 我发现了面试通关密码 #
306516次浏览 5898人参与
# 租房前辈的忠告 #
26049次浏览 1907人参与
# 我想象的工作vs实际工作 #
84027次浏览 1452人参与
# 比亚迪求职进展汇总 #
152832次浏览 1162人参与