$Luogu$

$Sol$

首先找出符合条件一的点然后跑$SPFA$就好了叭.

如何判断点是否符合条件一呢?先连反边,记录每个点的入度,然后从终点开始$dfs$,记录每个点被到达的次数,若到达的次数等于它的入度且不为$0$那么就是满足题意的.

为啥$Noip2014$有$4$道连我都觉得很水的题.

$Code$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i<=b;++i)
#define yes(i,a,b) for(Rg int i=a;i>=b;--i)
#define e(i,u) for(Rg int i=b[u];i;i=a[i].nt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147483647
using namespace std;
il int read()
{
Rg int x=,y=;char c=getchar();
while(c<''||c>''){if(c=='-')y=-;c=getchar();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
const int N=,M=;
int n,m,b[N],ct,du[N],s,t,vis[N],dis[N];
bool fl[N];
queue<int>q;
struct nd1{int u,v;}eg[M];
struct nd{int v,nt;}a[M];
il void add(int u,int v){a[++ct]=(nd){v,b[u]};b[u]=ct;}
il void dfs(int u)
{
e(i,u)
{
Rg int v=a[i].v;vis[v]++;
if(vis[v]>)continue;
dfs(v);
}
}
il void SPFA()
{
mem(vis,);mem(dis,);
vis[s]=;dis[s]=;q.push(s);
while(!q.empty())
{
Rg int u=q.front();q.pop();vis[u]=;
e(i,u)
{
Rg int v=a[i].v;
if(!fl[v])continue;
if(dis[v]>dis[u]+)
{
dis[v]=dis[u]+;
if(!vis[v]){vis[v]=;q.push(v);}
}
}
}
}
il bool cmp(nd1 x,nd1 y){return x.u==y.u?x.v<y.v:x.u<y.u;}
int main()
{
n=read(),m=read();
go(i,,m)
{
Rg int u=read(),v=read();
if(u==v)continue;
eg[i]=(nd1){u,v};//add(v,u);du[u]++;
}
sort(eg+,eg+m+,cmp);
Rg int nm=;
go(i,,m)
{
if(eg[i].u==eg[i-].u && eg[i].v==eg[i-].v){nm++;continue;}
add(eg[i].v,eg[i].u);du[eg[i].u]++;
}
m-=nm;
s=read(),t=read();swap(s,t);
vis[s]=;dfs(s);
go(i,,n)if((vis[i]==du[i]&&vis[i])||i==s)fl[i]=;
if(!fl[s]){printf("-1\n");return ;}
SPFA();
if(dis[t]>M)printf("-1\n");
else printf("%d\n",dis[t]);
return ;
}

最新文章

  1. 鱼眼模式(Fisheye projection)的软件实现
  2. 【7集iCore3基础视频】7-7 Qt5.2.1安装
  3. PhoneGap初试!
  4. canvas 实现 柱状图
  5. [CSS]如何正确使用ID和Class?
  6. C# 文件/文件夹压缩
  7. C#之自己定义的implicit和explicit转换
  8. Matlab.NET混合编程技巧之——找出Matlab内置函数
  9. CDH的安装
  10. java 集合框架(二)Iterable接口
  11. QT 5.9版本 使用MSVC2015编译时出现中文字符乱码问题的解决方法
  12. 使用Bandwagon服务器ftp解决git clone速度慢的问题
  13. ajaxToolkit 异步加载报 错误500的解决方法
  14. Java设计模式从精通到入门二 装饰器模式
  15. OpenJ_POJ C16G Challenge Your Template 迪杰斯特拉
  16. koa-connect源码解析
  17. JAVA虚拟机的生命周期
  18. VS生成事件执行XCOPY时出现Invalid num of parameters的解决方案
  19. C# 过滤sql特殊字符方法集合
  20. 从 Swift 中的序列到类型擦除

热门文章

  1. SDUT-3334_数据结构实验之栈与队列七:出栈序列判定
  2. postman 中post方式提交数据
  3. python深浅copy和赋值
  4. Python--day63--图书管理系统表结构设计
  5. Python--day30--网络基础
  6. java基本类型和String之间的转换
  7. Navicat for MySQL 使用SSH方式链接远程数据库(二)
  8. js(四) 全选/全不选和反选
  9. 2019-10-19-dotnet-给MatterMost订阅RSS博客
  10. Python--day37--守护进程和几个常用的方法