社区讨论
20分求救!!不知道哪里错了!
P2296[NOIP 2014 提高组] 寻找道路参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi7yo8ak
- 此快照首次捕获于
- 2025/11/21 05:46 4 个月前
- 此快照最后确认于
- 2025/11/21 05:46 4 个月前
rt!MLE+TLE。
CPP#include<iostream>
#include<queue>
#define maxn 10001
#define maxm 200001
using namespace std;
int head[maxn],cnt,ans;
int n,m,s,t;
queue<int> q;
bool used[maxn],pan[maxn],flag;
struct Edge{
int to,next;
}e[maxm];
void add(int from,int to)
{
e[++cnt].to=to;
e[cnt].next=head[from];
head[from]=cnt;
}
void dfs(int point)
{
if(point==s)
{
flag=true;
pan[s]=true;
return ;
}
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=e[j].next)
{
if(i==point) continue;
if(e[j].to==point)
{
pan[i]=true;
dfs(i);
}
}
}
void bfs(int s)
{
q.push(s);
while(!q.empty())
{
int now=q.front();
q.pop();
used[now]=true;
for(int i=head[now];i;i=e[i].next)
{
if(!used[e[i].to]&&pan[e[i].to]) q.push(e[i].to),used[e[i].to]=true;
ans++;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(x==y) continue;
add(x,y);
}
cin>>s>>t;
dfs(t);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=e[j].next)
if(!pan[e[j].to]) pan[i]=false;
bfs(s);
if(flag)
cout<<ans;
else
cout<<-1;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...