记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 1ms 328.0 KiB
#2 Accepted 1ms 328.0 KiB
#3 Accepted 1ms 208.0 KiB
#4 Accepted 1ms 328.0 KiB
#5 Accepted 1ms 340.0 KiB
#6 Accepted 1ms 332.0 KiB
#7 Accepted 2ms 340.0 KiB
#8 Accepted 11ms 896.0 KiB
#9 Accepted 3ms 568.0 KiB
#10 Accepted 44ms 2.215 MiB

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=200010;
int n,m,s,t,cnt;
int last[maxn],vis[maxn],dfn[maxn],inq[maxn],d[maxn];
struct Edge
{
  int to,nxt;
}a[maxm];

inline void Add(int x,int y)
{
  a[++cnt].to=y;
  a[cnt].nxt=last[x];
  last[x]=cnt;
}
void dfs(int x)
{
  dfn[x]=1;
  for(int i=last[x];i;i=a[i].nxt)
  {
  	int y=a[i].to;
  	if(dfn[y]) continue;
  	dfs(y);
  }
}

queue<int> q;
void bfs()
{
  d[t]=0;
  q.push(t);
  inq[t]=1;
  while(!q.empty())
  {
  	int x=q.front(); q.pop();
  	for(int i=last[x];i;i=a[i].nxt)
  	{
  	  int y=a[i].to;
	  if(!inq[y] && !vis[y])
	  {
	    inq[y]=1;
		d[y]=d[x]+1;
		q.push(y);	
	  }	
	}
  }
}

int main()
{
  int x,y;
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++)
  {
  	scanf("%d %d",&x,&y);
  	Add(y,x);
  }
  scanf("%d %d",&s,&t);
  dfs(t);
  for(int x=1;x<=n;x++)
    if(!dfn[x])
      for(int i=last[x];i;i=a[i].nxt)
	    vis[a[i].to]=1;	
  bfs();
  if(d[s]==0) printf("-1\n");
  else  printf("%d\n",d[s]);
  return 0;
}

信息

递交者
类型
递交
题目
P1025 寻找道路
比赛
随机真题赛第三轮(xhy&lfy讲题)
题目数据
下载
语言
C++
递交时间
2019-11-12 13:50:37
评测时间
2019-11-12 13:50:37
评测机
分数
100
总耗时
71ms
峰值内存
2.215 MiB