- 题解
- @ 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