- 题解
- 2018-09-10 19:57:30 @
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define inf 2100000000
using namespace std;
const int N=10005;
int d[N],v,w,n,m,x,judge[N],s,t;
struct point{
int cnt;
int cnt2;
int pre[N/3];
int to[N/3];
}p[N];
//floyd的优化,超快!
void spfa(int s)
{
for (int i=1;i<=n;i++) d[i]=inf;
d[s]=0;
queue <int> q;
q.push(s);
while (!q.empty())
{
x=q.front();//队首元素
q.pop();//弹出队首
for (int i=1;i<=p[x].cnt;i++)//遍历该点连接的点
{
v=p[x].to[i];
if (judge[v]) continue;
if (d[v]>d[x]+1)
{
d[v]=d[x]+1;
q.push(v);
}
}
}
}
//floyd的优化,超快!
void fspfa(int s)
{
for (int i=1;i<=n;i++) d[i]=inf;
d[s]=0;
queue <int> q;
q.push(s);
while (!q.empty())
{
x=q.front();//队首元素
q.pop();//弹出队首
for (int i=1;i<=p[x].cnt2;i++)//遍历该点连接的点
{
v=p[x].pre[i];
if (judge[v]) continue;
if (d[v]>d[x]+1)
{
d[v]=d[x]+1;
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
p[a].to[++p[a].cnt]=b;
p[b].pre[++p[b].cnt2]=a;
}
scanf("%d%d",&s,&t);
memset(judge,0,sizeof(judge));
fspfa(t);
if (d[s]==inf)
{
printf("-1\n");
return 0;
}
for (int i=1;i<=n;i++)
{
if (d[i]==inf)
{
judge[i]=1;
for (int j=1;j<=p[i].cnt2;j++)
{
judge[p[i].pre[j]]=1;
}
}
}
if (judge[s])
{
printf("-1\n");
return 0;
}
spfa(s);
if (d[t]!=inf) printf("%d\n",d[t]);
else printf("-1\n");
return 0;
}
1 条评论
-
PA_lotusbl LV 5 MOD @ 2018-09-10 19:58:16
哇,lz好棒,顶顶!d=====( ̄▽ ̄*)b
- 1